Each turing machine can be specified by the five elements:

- A finite set of symbols
*A*, also called the alphabet. - An initial symbol
*a*, which each cell contains on initialization._{init} - A finite set of states
*S*. - An initial state
*s*._{init} - A final state
*s*._{final} - A function
~~f~~of state and symbols onto a tupple consisting of a new state, a new symbol, and a movement. The movement can be one of**right**and**left**.

Many interesting properties of Turing Machines have been proven so far. For example, that each Turing Machine can be transformed into a Turing Machine with a tape that is cut-off on one side, and endless on the other side. Or that every Turing machine can be transformed into a Turing machine with set of symbols contains just two symbols.

A language is said to be 'Turing-complete', if for each functions that can be calculated with a Turing Machine, it can be shown that there is a program in this language that performs the same function. There are basically three approaches to proof that a language is Turing-complete. These are:

- Show there is some mapping from each possible Turing machine to a program in the language.
- Show that there is a program in the language that emulates a Universal Turing Machine.
- Show that the language is equivalent with (or a superset of) a language that is known to be Turing-complete.

To achieve this, the set of symbols *A* is mapped onto the
numbers 0 to *n*-1, where *n* equals the number of
symbols, such that *a _{init}* maps onto zero.
Likewise, the set of states

To simulate a Turing machine, we need an array with unlimited
length to represent the tape, a index into that array representing
the position of the head, and the current state.
To program this in BF we will need to assign these to some
memory locations. The position of the head will be stored
in memory location ` head`, and the current state
in the memory location

Not(t1,t2,t3)

while(t2)

(some code which given the state and the cursymbol

assigns a value to newstate, newsymbol, and newhead)

*setarray(base,1,0,newhead,newsymbol)
zero(cursymbol)
zero(newsymbol)
zero(head) move(newhead,head,t1)
zero(state) move(newstate,state,t1)
*

*
IsOne(state,t1)
Not(t1,t2,t3)*

Where, given the tupplemap(state,head,cursymbol, i,j,k,l,m, newstate,newhead,newsymbol)

In this code the expressionmap(state,head,cursymbol, astate,asymbol,anewstate,anewsymbol,movement, newstate,newhead,newsymbol)=copy(state,t1,t2) const(t2,astate) Equal(t1,t2,t3,t4,t5) if(t3) copy(cursymbol,t1,t2) const(t2,asymbol) Equal(t1,t2,t3,t4,t5) if(t3) const(newstate,anewstate) const(newsymbol,anewsymbol) copy(head,newhead,t1) ifelse(movement,t1) inc(newhead) else(movement,t1) dec(newhead) endelse(t1) endif(t3) endif(t3)

this fully documented BF program written by Daniel B. Cristofani. |

A Universal Turing Machine (UTM) is a Turing machine that can
simulate some Turing-complete computational model. By giving
a BF program which simulates a particular UTM, we proof
that BF is Turing-complete. The UTM that we implement here is
taken from from Yurii Rogozhin's article
*Small universal Turing machines*, in Theoretical Computer
Science, November 1996 (volume 168 pgs 215-240).
This UTM simulate a Turing-complete class of tag-systems.
A tag-system transforms strings over an alphabet
A = {a[1],a[2],...,a[n], a[n+1]} as follows: a positive
integer m is chosen, and so is a function P that maps
each a[i] for 1<=i<=n to a string P(a[i]) over
the alphabet A. Now:

- if the string being transformed has fewer than m elements, the whole process stops now.
- m elements are removed from the beginning of the string
- call the first element removed a[k]; if k=n+1 the whole process stops now.
- P(a[k]) is appended to the string.
- steps 1-5 are repeated.

The input for this Turing machine is mildly complex, and there is no error checking.

- The representation of a symbol a[i] from the alphabet
A is a string of 1s which is one element longer than
twice the combined length of all P(a[j]) where
1<=j<i.
- a value like P(a[i]) = a[n]a[n]a[w]a[x]...a[y]a[z] is
represented as follows:
`b 1`

`b 111...`(as many as required to represent a[z] as described above)`b`

`b 111...`(to represent a[y] as described above)`b`

`.`

`.`

`.`

`b 111...`(to represent a[x])`b`

`b 111...`(to represent a[w])`b`

`b 111...`(to represent a[n])`b`

`b 111...`(as many as for a[n] as described above, MINUS the number of 1s that represent a[i]; and no final b) - The function P is represented by listing all its
outputs in the order P(a[n]), P(a[n-1]),...,P(a[2]),P(a[1]).
The representation of P(a[n+1])=STOP is done for you.
- The initial string a[q]a[r]...a[s]a[t] to be transformed
by the tag-system is represented as
`111...`(as many as required to represent a[q] as above)`c`

`111...`(to represent a[r])`c`

`.`

`.`

`.`

`111...`(to represent a[s])`c`

`111...`(to represent a[t]; note that there is no final c.) - The input to this program is a function P as described above,
then a single b, then the initial string to be transformed.
Run all the 1s, bs, and cs together in one line with nothing between,
followed by a return.
- The output format, if the program terminates, is the same as the input format for the initial string, and represents the final state of the transformed string, with a final a[n+1] appended due to a peculiarity of the Turing machine's algorithm.

P(a[1]) = a[3]a[3]a[2]a[1]a[4]

P(a[2]) = a[3]a[3]a[1]

P(a[3]) = a[3]a[3]

P(a[4]) = STOP

It meets the criteria above; and when applied to the initial string a[2]a[1]a[1] it gives:

a[2]a[1]a[1] a[1]a[3]a[3]a[1] a[3]a[1]a[3]a[3]a[2]a[1]a[4] a[3]a[3]a[2]a[1]a[4]a[3]a[3] a[2]a[1]a[4]a[3]a[3]a[3]a[3] a[4]a[3]a[3]a[3]a[3]a[3]a[3]a[1] a[3]a[3]a[3]a[3]a[3]a[1]and then it's done.

Now, the encoding:

a[1] is 1 a[2] is 11111111111 a[3] is 11111111111111111 a[4] is 111111111111111111111 P(a[1]) is b1 b111111111111111111111b b1b b11111111111b b11111111111111111b b1111111111111111 P(a[2]) is b1 b1b b11111111111111111b b111111 P(a[3]) is b1 b11111111111111111b bthe initial string is

and so the whole input is

b1 b11111111111111111b b b1 b1b b11111111111111111b b111111 b1 b111111111111111111111b b1b b11111111111b b11111111111111111b b1111111111111111 b 11111111111c1c1which when run together for input to the Turing machine becomes

b1b11111111111111111bbb1b1bb11111111111111111bb111111b1b111111111111111111111bb1bb11111111111bb11111111111111111bb1111111111111111b11111111111c1c1

11<L1 | 210R2 | 311R3 | 410R4 |

1b>R1 | 2b>L3 | 3b<R4 | 4bcL2 |

1>bL1 | 2><R2 | 3>bR3 | 4><R4 |

1<0R1 | 2<>L2 | 3< H | 4< |

10<L1 | 201L2 | 30cR1 | 40cL2 |

1c0R4 | 2cbR2 | 3c1R1 | 4cbR4 |

The minimal test case b1b1bbb1c1c11111 represents the tag-system where P(a[1]) = a[1]a[1] and P(a[2]) = STOP, applied to the string a[1]a[1]a[2]. This runs for 518 steps of the Turing machine, exercising all 23 Turing machine instructions, before halting with the output string a[1].

+++>++>>>+[>>,[>+++++<[[->]<<]<[>]>]>-[<<+++++>>-[<<---->>-[->]<]] <[<-<[<]+<+[>]<<+>->>>]<]<[<]>[-[>++++++<-]>[<+>-]+<<<+++>+> [- [<<+>->- [<<[-]>>- [<<++>+>- [<<-->->>+++<- [<<+>+>>--<- [<<->->- [<<++++>+>>+<- [>-<- [<<->->- [<<->>- [<<+++>>>-<- [<<---->>>++<- [<<++>>>+<- [>[-]<- [<<->>>+++<- [<<->>>--<- [<<++++>+>>+<- [<<[-]>->>++<- [<<+++++>+>>--<- [<->>++< [<<->>- ]]]]]]]]]]]]]]]]]]]]]]<[->>[<<+>>-]<<<[>>>+<<<-]<[>>>+<<<-]]>>] >[-[---[-<]]>]>[+++[<+++++>--]>]+<++[[>+++++<-]<]>>[-.>]

The Universal Register Machine is a machine with a fixed number of characters, and it supports the following commands:

`a`: increment register*n**n*`s`: decrement register*n**n*: execute command*x*;*y*and then*x**y*`(`: execute command*x*)*n*while register*x*is nonzero*n*`.`: ("dot blank") halt the machine.

- Add register 3 to register 2:
(a2;s3)3.

- Multiply register 2 with register 3:
(a4;a5;s2)2; ((a2;s4)4; s3; (a1;a4;s5)5; (a5;s1)1)3.

There is almost a one-to-one mapping from URM to BF.
The `a n` expression maps to

- Add register 3 to register 2:
>>>[<+>-]<<<

- Multiply register 2 with register 3:
>>[>>+>+<<<-]>[>[<<+>>-]<->>[<<<<+>>>+>-]<<<<[>>>>+<<<<-]>>]<<<

It is possible to make context free grammars for both BF and URM, such that matching parse trees indicate equivalent programs. Such a grammar is given below:

URM | BF |

root = S._{1} |
root = S_{1} |

S = a_{n}n |
S = +_{n} |

S = s_{n}n |
S = -_{n} |

S = _{n}S ; _{n}S_{n} |
S = _{n}S _{n}S_{n} |

S = ( _{n}S )_{n}n |
S = [ _{n}S ]_{n} |

S = _{n}S _{n+1} |
S = > _{n}S <_{n+1} |

S = _{n}S _{n-1} |
S = < _{n}S >_{n-1} |

Using this mapping, one can create another UTM in BF from the above mentioned UTM in URM.

Still, I feel that BF is far more elegant than URM, because it gives you more with less symbols. BF only needs the symbols "+", "-", "<", ">", "[", and "]", whereas URM needs "a", "s", ";", "(", ")", ".", and "0" to "9". Although, I have to admit, that BF programs will in general be longer than the equivalent URM program, and in most cases also more cryptic.

home and email