BETROTHED                                        
                                        ----*----
                           uncertainly turing complete esolang
                                      Conor O'Brien
                                        ----*----

TABLE OF CONTENTS

   I.   INTRODUCTION
   II.  PROGRAM REQUIREMENTS
   III. DEFINITIONS
   IV.  PROGRAM EXECUTION
   V.   PROOF OF TURING COMPLETENESS

I. INTRODUCTION
Betrothed is an esoteric language intended to be "unprovably Turing Complete", assuming
infinite memory. I have attempted to make the language not terribly convoluted by
limiting the uncertain parts of the language to the lengths of the line pairs. To make
the esolang more interesting, I have also restricted the source of the program. Further,
it is also interesting to note that the mode of execution is, as far as I know, is a new
thing.

    Just as a warning, this document provides a more rigorous specification of the
language. If you do not like symbols, well, shucks.

                                        ----*----

II. PROGRAM REQUIREMENTS
Any Betrothed program must consist of only the following characters, to include the space:

    {} [] () <> + = ;
    
    All semicolons (;) are replaced with newlines before parsing.

    The program must have an even number of lines. A line is defined to be a sequence of 
characters terminated by the a newline, optionally preceeded by a carriage return. If the
program does not end with such a sequence, the EOF is treated as a newline.

    The program is parsed in pairs of lines. For each pair of lines  (M, N) , the 
lengths  m  and  n  of  the respective lines must satisfy one of the following conditions:

  - both are pairs of betrothed numbers ( σ(m) = σ(n) = m + n + 1 , where
    σ(k) = sum of the divisors of k )
  - both are twin primes  ( m  is prime,  n  is prime, and  m = n + 2 )

and must satisfy:

  - no other two lines in a pair  (M', N')  with lengths  m'  and  n'  exist in the 
    program such that  (m, n) = (m', n')  or  (m, n) = (n', m') .

                                        ----*----

III. DEFINITIONS

Before detailing the execution of the program, I will go into some preliminary definitions.

    Let  '...'  denote a string of characters. For example,  'Hello'  is a string of the
characters "H", "e", "l", "l", and "o".

    Let  undef  represent an undefined value; when a program encounters this value, it
may either error or have undefined behaviour. 

    Let  #S  denote the length of a string  S . For example,  #'Hello' = 5.

    Let  S . T  denote the concatenation of two strings  S  and  T . For example,
 'He' . 'llo' = 'Hello' .

    Let  k { S  denote the zero-indexed  k th character in S. For example,
 0 { 'Hello' = 'H' .

    Let  k } S  denote all but the  k th character in S. For example,
 0 } 'Hello' = 'ello' .

    Let  sub(T, j, k)  be the slice of a string  T  from index  j  to index  j + k . For
example,  sub('Hello', 2, 2) = 'll' .

    (Conventional operations on strings remain evident:  S = T  for equality,  S /= T
for inequality, etc.)

    Let  S <= T  be true for strings  S  and  T  when there exists at least one index  i
for which  sub(T, i, #S) = S , and false otherwise.

    Let  P & Q  denote the conjunction of two predicates, and  P | Q  the disjunction of
two predicates.

    Let  rev(S)  denote the reversed order of characters of a string  S .

    Let  rep(S, t1, t2)  denote the replacement of all substrings  t1  in  S  with  t2 .
For example,  rep('3.141514', '14', '$') = '3.$15$' .

Let:

                    {  undef                                if #t1 /= #t2
    tr(S, t1, t2) = {  tr(rep(S, 0{t1, 0{t2), 0}t1, 0}t2)   if #t1 > 0
                    {  S                                    if #t1 = 0

Let the "mirror" operation be defined as:

    mir(S) = tr(rev(S), '<>{}()[]', '><}{)(][')

Let:

                 {  rot(sub(S, 1, #S - 1) . (0 { S), n - 1)  if n > 0
    rot(S, n) =  {  S                                        if n = 0
                 {  rev(rot(S, #S + n))                      if n < 0

Let  S  be a "shift" of  T  if and only if, for some  0 <= n < #S ,  rot(S, n) = T .

A string  S  a "pliable subset" of a string  T  if and only if, for any shift  S'  of  S :

    (S' <= T) | (mir(S') <= T)

 S'  here is called a "pliable factor" of  T  with respect to  S . For example,  'ABB'
is a pliable subset of  'BBAB' , since  'BBA'  is a shift of  'ABB'  and a subset of  
'BBAB' .

                                        ----*----

IV. PROGRAM EXECUTION

Now, for the program execution specification. Suppose Betrothed has a set of commands,
hereafter referred to as  CMDS . I will define the actual commands later, to be used in
this incarnation of the language.

    For each of the aforementioned pairs  (M, N) , the following algorithm is performed:

  1. Call  Q  the set of (possibly overlapping) pliable factors of  M  with respect to  N .
  2. Let  q = #Q .
  3. Remove all such pliable factors from  N  and call this new string N' .
  4. Call  d  the levenshtein distance between  N  and  N' .
  5. Let  F  be the  q th command in  CMDS . Then, call  F(d) .



                                        ----*----

Betrothed manipulates a stack. Popping from an empty stack gives a zero.

                                        ----*----

This is the list of commands used in this incarnation of betrothed. (Note that index = 
 q  from before.) Here,  z = d - q .

          +-------+------------+-----------------------------------------------+
          | index | name       | effect                                        |
          +=======+============+===============================================+
          | 0     | input      | pop x; push x'th data argument*               |
          | 1     | outnum     | pop x; output x                               |
          | 2     | pushnum    | push z                                        |
          | 3     | outchr     | pop x; output x as an ASCII character         |
          | 4     | jump       | jumps to line pair d                          |
          | 5     | popjump    | pop x; jumps to line pair x                   |
          | 6     | if         | peek x; if x != 0, execute next statement     |
          | 7     | pick       | pops x; pushes the x'th element in the stack  |
          | 8     | multiply   | pop x; push x * z                             |
          | 9     | add        | pop x; push x + z                             |
          | 10    | subtract   | pop x; push x - z                             |
          | 11    | divide     | pop x; push x / z                             |
          | 12    | duplicate  | pop x; "push x" z times                       |
          | 13    | outstack   | display the contents of the stack             |
          | 14    | exit       | terminates program                            |
          | 15    | exitcode   | exits with code z                             |
          | 16    | drop       | pop x                                         |
          | 17    | exec       | pop y; pop x; executes instruction x with y   |
          | 18    | diagnostic | pushes the z'th information diagnostic**      |
          +-------+------------+-----------------------------------------------+

* the first data argument being the first argument that is not the name of the file, and is
passed to the betrothed interpreter. The argument is parsed as a number (up to the
implementation as to how the number exactly is parsed), and if no number can be validly
parsed, the program should error. Below are marked the data arguments, valid or invalid:

    betrothed file.bet 3 5 asdf foo 9
                       ^ ^ ^^^^ ^^^ ^
    
** The information diagnostics are:

  0. size of stack
  1. current index in program
  2. current year (full)
  3. current month (1 is January)
  4. current day
  5. current hours
  6. current minutes
  7. current seconds
  8. current nanoseconds

                                        ----*----

V. PROOF OF TURING COMPLETENESS

Now, no language can be Turing Complete with bounded program size. Therefore, if Betrothed
is Turing Complete, it must have unbounded program size. Since the lengths of the lines of
a Betrothed program must be twin prime pairs or betrothed pairs, and since both sequences
are unproven to be infinite or finite, Betrothed has unbounded program size if and only if
there are infintie betrothed pairs, there are infinite twin prime pairs, or both.

    Next: to prove that if Betrothed has an unbounded program size, then it is Turing
Complete. I will use the op-codes from the above table to demonstrate key factors of a
Turing Complete language; they are of the form  [index]<[ld]> .

  1. Conditional goto: 6<> 5<>, or if-popjump. This can be used to form a loop.
  2. Inequality to a constant K: 10<K> 
  3. Arbitrarily large variable space: you can use some separator constant C.

    With this, I have sufficient reason to believe that Betrothed is Turing Complete.