84 lines
2.1 KiB
Plaintext
84 lines
2.1 KiB
Plaintext
One of the foundational mathematical constructs behind computer science
|
||
is the [[wp:Universal Turing machine|universal Turing Machine]].
|
||
|
||
|
||
(Alan Turing introduced the idea of such a machine in 1936–1937.)
|
||
|
||
Indeed one way to definitively prove that a language
|
||
is [[wp:Turing_completeness|turing-complete]]
|
||
is to implement a universal Turing machine in it.
|
||
|
||
|
||
;Task:
|
||
Simulate such a machine capable
|
||
of taking the definition of any other Turing machine and executing it.
|
||
|
||
Of course, you will not have an infinite tape,
|
||
but you should emulate this as much as is possible.
|
||
|
||
The three permissible actions on the tape are "left", "right" and "stay".
|
||
|
||
To test your universal Turing machine (and prove your programming language
|
||
is Turing complete!), you should execute the following two Turing machines
|
||
based on the following definitions.
|
||
|
||
|
||
'''Simple incrementer'''
|
||
* '''States:''' q0, qf
|
||
* '''Initial state:''' q0
|
||
* '''Terminating states:''' qf
|
||
* '''Permissible symbols:''' B, 1
|
||
* '''Blank symbol:''' B
|
||
* '''Rules:'''
|
||
** (q0, 1, 1, right, q0)
|
||
** (q0, B, 1, stay, qf)
|
||
|
||
<br>
|
||
The input for this machine should be a tape of <code>1 1 1</code>
|
||
|
||
|
||
'''Three-state busy beaver'''
|
||
* '''States:''' a, b, c, halt
|
||
* '''Initial state:''' a
|
||
* '''Terminating states:''' halt
|
||
* '''Permissible symbols:''' 0, 1
|
||
* '''Blank symbol:''' 0
|
||
* '''Rules:'''
|
||
** (a, 0, 1, right, b)
|
||
** (a, 1, 1, left, c)
|
||
** (b, 0, 1, left, a)
|
||
** (b, 1, 1, right, b)
|
||
** (c, 0, 1, left, b)
|
||
** (c, 1, 1, stay, halt)
|
||
|
||
<br>
|
||
The input for this machine should be an empty tape.
|
||
|
||
|
||
'''Bonus:'''
|
||
|
||
'''5-state, 2-symbol probable Busy Beaver machine from Wikipedia'''
|
||
* '''States:''' A, B, C, D, E, H
|
||
* '''Initial state:''' A
|
||
* '''Terminating states:''' H
|
||
* '''Permissible symbols:''' 0, 1
|
||
* '''Blank symbol:''' 0
|
||
* '''Rules:'''
|
||
** (A, 0, 1, right, B)
|
||
** (A, 1, 1, left, C)
|
||
** (B, 0, 1, right, C)
|
||
** (B, 1, 1, right, B)
|
||
** (C, 0, 1, right, D)
|
||
** (C, 1, 0, left, E)
|
||
** (D, 0, 1, left, A)
|
||
** (D, 1, 1, left, D)
|
||
** (E, 0, 1, stay, H)
|
||
** (E, 1, 0, left, A)
|
||
|
||
<br>
|
||
The input for this machine should be an empty tape.
|
||
|
||
This machine runs for more than 47 millions steps.
|
||
<br><br>
|
||
|