Universal Turing machine: Difference between revisions

Content added Content deleted
(Added 11l)
Line 80: Line 80:
This machine runs for more than 47 millions steps.
This machine runs for more than 47 millions steps.
<br><br>
<br><br>

=={{header|11l}}==
{{trans|Python}}

<lang 11l>F run_utm(halt, state, Char blank; rules_in, [Char] &tape = [Char](); =pos = 0)
V st = state
I tape.empty
tape.append(blank)
I pos < 0
pos += tape.len
V rules = Dict(rules_in, r -> ((r[0], Char(r[1])), (Char(r[2]), r[3], r[4])))

L
print(st.ljust(4), end' ‘ ’)
L(v) tape
V i = L.index
I i == pos
print(‘[’v‘]’, end' ‘ ’)
E
print(v, end' ‘ ’)
print()

I st == halt
L.break
I (st, tape[pos]) !C rules
L.break

V (v1, dr, s1) = rules[(st, tape[pos])]
tape[pos] = v1
I dr == ‘left’
I pos > 0
pos--
E
tape.insert(0, blank)
I dr == ‘right’
pos++
I pos >= tape.len
tape.append(blank)
st = s1

print("incr machine\n")
run_utm(
halt' ‘qf’,
state' ‘q0’,
blank' Char(‘B’),
rules_in' [‘q0 1 1 right q0’.split(‘ ’, group_delimiters' 1B),
‘q0 B 1 stay qf’.split(‘ ’, group_delimiters' 1B)],
tape' &[‘1’, ‘1’, ‘1’]
)

print("\nbusy beaver\n")
run_utm(
halt' ‘halt’,
state' ‘a’,
blank' Char(‘0’),
rules_in'
[‘a 0 1 right b’.split(‘ ’, group_delimiters' 1B),
‘a 1 1 left c’.split(‘ ’, group_delimiters' 1B),
‘b 0 1 left a’.split(‘ ’, group_delimiters' 1B),
‘b 1 1 right b’.split(‘ ’, group_delimiters' 1B),
‘c 0 1 left b’.split(‘ ’, group_delimiters' 1B),
‘c 1 1 stay halt’.split(‘ ’, group_delimiters' 1B)]
)

print("\nsorting test\n")
run_utm(
halt' ‘STOP’,
state' ‘A’,
blank' Char(‘0’),
rules_in'
[‘A 1 1 right A’.split(‘ ’, group_delimiters' 1B),
‘A 2 3 right B’.split(‘ ’, group_delimiters' 1B),
‘A 0 0 left E’.split(‘ ’, group_delimiters' 1B),
‘B 1 1 right B’.split(‘ ’, group_delimiters' 1B),
‘B 2 2 right B’.split(‘ ’, group_delimiters' 1B),
‘B 0 0 left C’.split(‘ ’, group_delimiters' 1B),
‘C 1 2 left D’.split(‘ ’, group_delimiters' 1B),
‘C 2 2 left C’.split(‘ ’, group_delimiters' 1B),
‘C 3 2 left E’.split(‘ ’, group_delimiters' 1B),
‘D 1 1 left D’.split(‘ ’, group_delimiters' 1B),
‘D 2 2 left D’.split(‘ ’, group_delimiters' 1B),
‘D 3 1 right A’.split(‘ ’, group_delimiters' 1B),
‘E 1 1 left E’.split(‘ ’, group_delimiters' 1B),
‘E 0 0 right STOP’.split(‘ ’, group_delimiters' 1B)],
tape' &‘2 2 2 1 2 2 1 2 1 2 1 2 1 2’.split(‘ ’).map(Char)
)</lang>

{{out}}
<pre style="height:30ex;overflow:scroll">
incr machine

q0 [1] 1 1
q0 1 [1] 1
q0 1 1 [1]
q0 1 1 1 [B]
qf 1 1 1 [1]

busy beaver

a [0]
b 1 [0]
a [1] 1
c [0] 1 1
b [0] 1 1 1
a [0] 1 1 1 1
b 1 [1] 1 1 1
b 1 1 [1] 1 1
b 1 1 1 [1] 1
b 1 1 1 1 [1]
b 1 1 1 1 1 [0]
a 1 1 1 1 [1] 1
c 1 1 1 [1] 1 1
halt 1 1 1 [1] 1 1

sorting test

A [2] 2 2 1 2 2 1 2 1 2 1 2 1 2
B 3 [2] 2 1 2 2 1 2 1 2 1 2 1 2
B 3 2 [2] 1 2 2 1 2 1 2 1 2 1 2
B 3 2 2 [1] 2 2 1 2 1 2 1 2 1 2
B 3 2 2 1 [2] 2 1 2 1 2 1 2 1 2
B 3 2 2 1 2 [2] 1 2 1 2 1 2 1 2
B 3 2 2 1 2 2 [1] 2 1 2 1 2 1 2
B 3 2 2 1 2 2 1 [2] 1 2 1 2 1 2
B 3 2 2 1 2 2 1 2 [1] 2 1 2 1 2
B 3 2 2 1 2 2 1 2 1 [2] 1 2 1 2
B 3 2 2 1 2 2 1 2 1 2 [1] 2 1 2
B 3 2 2 1 2 2 1 2 1 2 1 [2] 1 2
B 3 2 2 1 2 2 1 2 1 2 1 2 [1] 2
B 3 2 2 1 2 2 1 2 1 2 1 2 1 [2]
B 3 2 2 1 2 2 1 2 1 2 1 2 1 2 [0]
C 3 2 2 1 2 2 1 2 1 2 1 2 1 [2] 0
C 3 2 2 1 2 2 1 2 1 2 1 2 [1] 2 0
D 3 2 2 1 2 2 1 2 1 2 1 [2] 2 2 0
D 3 2 2 1 2 2 1 2 1 2 [1] 2 2 2 0
D 3 2 2 1 2 2 1 2 1 [2] 1 2 2 2 0
D 3 2 2 1 2 2 1 2 [1] 2 1 2 2 2 0
D 3 2 2 1 2 2 1 [2] 1 2 1 2 2 2 0
D 3 2 2 1 2 2 [1] 2 1 2 1 2 2 2 0
D 3 2 2 1 2 [2] 1 2 1 2 1 2 2 2 0
D 3 2 2 1 [2] 2 1 2 1 2 1 2 2 2 0
D 3 2 2 [1] 2 2 1 2 1 2 1 2 2 2 0
D 3 2 [2] 1 2 2 1 2 1 2 1 2 2 2 0
D 3 [2] 2 1 2 2 1 2 1 2 1 2 2 2 0
D [3] 2 2 1 2 2 1 2 1 2 1 2 2 2 0
A 1 [2] 2 1 2 2 1 2 1 2 1 2 2 2 0
B 1 3 [2] 1 2 2 1 2 1 2 1 2 2 2 0
B 1 3 2 [1] 2 2 1 2 1 2 1 2 2 2 0
B 1 3 2 1 [2] 2 1 2 1 2 1 2 2 2 0
B 1 3 2 1 2 [2] 1 2 1 2 1 2 2 2 0
B 1 3 2 1 2 2 [1] 2 1 2 1 2 2 2 0
B 1 3 2 1 2 2 1 [2] 1 2 1 2 2 2 0
B 1 3 2 1 2 2 1 2 [1] 2 1 2 2 2 0
B 1 3 2 1 2 2 1 2 1 [2] 1 2 2 2 0
B 1 3 2 1 2 2 1 2 1 2 [1] 2 2 2 0
B 1 3 2 1 2 2 1 2 1 2 1 [2] 2 2 0
B 1 3 2 1 2 2 1 2 1 2 1 2 [2] 2 0
B 1 3 2 1 2 2 1 2 1 2 1 2 2 [2] 0
B 1 3 2 1 2 2 1 2 1 2 1 2 2 2 [0]
C 1 3 2 1 2 2 1 2 1 2 1 2 2 [2] 0
C 1 3 2 1 2 2 1 2 1 2 1 2 [2] 2 0
C 1 3 2 1 2 2 1 2 1 2 1 [2] 2 2 0
C 1 3 2 1 2 2 1 2 1 2 [1] 2 2 2 0
D 1 3 2 1 2 2 1 2 1 [2] 2 2 2 2 0
D 1 3 2 1 2 2 1 2 [1] 2 2 2 2 2 0
D 1 3 2 1 2 2 1 [2] 1 2 2 2 2 2 0
D 1 3 2 1 2 2 [1] 2 1 2 2 2 2 2 0
D 1 3 2 1 2 [2] 1 2 1 2 2 2 2 2 0
D 1 3 2 1 [2] 2 1 2 1 2 2 2 2 2 0
D 1 3 2 [1] 2 2 1 2 1 2 2 2 2 2 0
D 1 3 [2] 1 2 2 1 2 1 2 2 2 2 2 0
D 1 [3] 2 1 2 2 1 2 1 2 2 2 2 2 0
A 1 1 [2] 1 2 2 1 2 1 2 2 2 2 2 0
B 1 1 3 [1] 2 2 1 2 1 2 2 2 2 2 0
B 1 1 3 1 [2] 2 1 2 1 2 2 2 2 2 0
B 1 1 3 1 2 [2] 1 2 1 2 2 2 2 2 0
B 1 1 3 1 2 2 [1] 2 1 2 2 2 2 2 0
B 1 1 3 1 2 2 1 [2] 1 2 2 2 2 2 0
B 1 1 3 1 2 2 1 2 [1] 2 2 2 2 2 0
B 1 1 3 1 2 2 1 2 1 [2] 2 2 2 2 0
B 1 1 3 1 2 2 1 2 1 2 [2] 2 2 2 0
B 1 1 3 1 2 2 1 2 1 2 2 [2] 2 2 0
B 1 1 3 1 2 2 1 2 1 2 2 2 [2] 2 0
B 1 1 3 1 2 2 1 2 1 2 2 2 2 [2] 0
B 1 1 3 1 2 2 1 2 1 2 2 2 2 2 [0]
C 1 1 3 1 2 2 1 2 1 2 2 2 2 [2] 0
C 1 1 3 1 2 2 1 2 1 2 2 2 [2] 2 0
C 1 1 3 1 2 2 1 2 1 2 2 [2] 2 2 0
C 1 1 3 1 2 2 1 2 1 2 [2] 2 2 2 0
C 1 1 3 1 2 2 1 2 1 [2] 2 2 2 2 0
C 1 1 3 1 2 2 1 2 [1] 2 2 2 2 2 0
D 1 1 3 1 2 2 1 [2] 2 2 2 2 2 2 0
D 1 1 3 1 2 2 [1] 2 2 2 2 2 2 2 0
D 1 1 3 1 2 [2] 1 2 2 2 2 2 2 2 0
D 1 1 3 1 [2] 2 1 2 2 2 2 2 2 2 0
D 1 1 3 [1] 2 2 1 2 2 2 2 2 2 2 0
D 1 1 [3] 1 2 2 1 2 2 2 2 2 2 2 0
A 1 1 1 [1] 2 2 1 2 2 2 2 2 2 2 0
A 1 1 1 1 [2] 2 1 2 2 2 2 2 2 2 0
B 1 1 1 1 3 [2] 1 2 2 2 2 2 2 2 0
B 1 1 1 1 3 2 [1] 2 2 2 2 2 2 2 0
B 1 1 1 1 3 2 1 [2] 2 2 2 2 2 2 0
B 1 1 1 1 3 2 1 2 [2] 2 2 2 2 2 0
B 1 1 1 1 3 2 1 2 2 [2] 2 2 2 2 0
B 1 1 1 1 3 2 1 2 2 2 [2] 2 2 2 0
B 1 1 1 1 3 2 1 2 2 2 2 [2] 2 2 0
B 1 1 1 1 3 2 1 2 2 2 2 2 [2] 2 0
B 1 1 1 1 3 2 1 2 2 2 2 2 2 [2] 0
B 1 1 1 1 3 2 1 2 2 2 2 2 2 2 [0]
C 1 1 1 1 3 2 1 2 2 2 2 2 2 [2] 0
C 1 1 1 1 3 2 1 2 2 2 2 2 [2] 2 0
C 1 1 1 1 3 2 1 2 2 2 2 [2] 2 2 0
C 1 1 1 1 3 2 1 2 2 2 [2] 2 2 2 0
C 1 1 1 1 3 2 1 2 2 [2] 2 2 2 2 0
C 1 1 1 1 3 2 1 2 [2] 2 2 2 2 2 0
C 1 1 1 1 3 2 1 [2] 2 2 2 2 2 2 0
C 1 1 1 1 3 2 [1] 2 2 2 2 2 2 2 0
D 1 1 1 1 3 [2] 2 2 2 2 2 2 2 2 0
D 1 1 1 1 [3] 2 2 2 2 2 2 2 2 2 0
A 1 1 1 1 1 [2] 2 2 2 2 2 2 2 2 0
B 1 1 1 1 1 3 [2] 2 2 2 2 2 2 2 0
B 1 1 1 1 1 3 2 [2] 2 2 2 2 2 2 0
B 1 1 1 1 1 3 2 2 [2] 2 2 2 2 2 0
B 1 1 1 1 1 3 2 2 2 [2] 2 2 2 2 0
B 1 1 1 1 1 3 2 2 2 2 [2] 2 2 2 0
B 1 1 1 1 1 3 2 2 2 2 2 [2] 2 2 0
B 1 1 1 1 1 3 2 2 2 2 2 2 [2] 2 0
B 1 1 1 1 1 3 2 2 2 2 2 2 2 [2] 0
B 1 1 1 1 1 3 2 2 2 2 2 2 2 2 [0]
C 1 1 1 1 1 3 2 2 2 2 2 2 2 [2] 0
C 1 1 1 1 1 3 2 2 2 2 2 2 [2] 2 0
C 1 1 1 1 1 3 2 2 2 2 2 [2] 2 2 0
C 1 1 1 1 1 3 2 2 2 2 [2] 2 2 2 0
C 1 1 1 1 1 3 2 2 2 [2] 2 2 2 2 0
C 1 1 1 1 1 3 2 2 [2] 2 2 2 2 2 0
C 1 1 1 1 1 3 2 [2] 2 2 2 2 2 2 0
C 1 1 1 1 1 3 [2] 2 2 2 2 2 2 2 0
C 1 1 1 1 1 [3] 2 2 2 2 2 2 2 2 0
E 1 1 1 1 [1] 2 2 2 2 2 2 2 2 2 0
E 1 1 1 [1] 1 2 2 2 2 2 2 2 2 2 0
E 1 1 [1] 1 1 2 2 2 2 2 2 2 2 2 0
E 1 [1] 1 1 1 2 2 2 2 2 2 2 2 2 0
E [1] 1 1 1 1 2 2 2 2 2 2 2 2 2 0
E [0] 1 1 1 1 1 2 2 2 2 2 2 2 2 2 0
STOP 0 [1] 1 1 1 1 2 2 2 2 2 2 2 2 2 0
</pre>


=={{header|Ada}}==
=={{header|Ada}}==
Retrieved from "https://rosettacode.org/wiki/Universal_Turing_machine"