Universal Turing machine: Difference between revisions
Content added Content deleted
(Removed useless clones() from rust solution) |
(adding lambdatalk) |
||
Line 4,837:
(Only the first 20 lines displayed)
</pre>
=={{header|Lambdatalk}}==
<lang scheme>
{require lib_H} ;; associative arrays library
{def tm
{def tm.r
{lambda {:data :rules :state :end :blank :i :N}
{if {or {W.equal? :state :end} {> :N 100}}
then :data
else {let { {:name :name} {:data :data}
{:end :end} {:blank :blank} {:rules :rules}
{:i :i} {:nb :nb}
{:state {H.get :state :rules}}
{:cell {if {W.equal? {A.get :i :data} undefined}
then :blank
else {A.get :i :data}}}
} {tm.r {A.set! :i {H.get write {H.get :cell :state}} :data}
:rules
{H.get next {H.get :cell :state}}
:end
:blank
{+ :i {H.get move {H.get :cell :state}} }
{+ :N 1} } }}}}
{lambda {:name :data :rules :state :end :blank}
:name: {A.duplicate :data} ->
{tm.r :data :rules :state :end :blank 0 0}}}
-> tm
{tm zero2one
{A.new 0 0 0}
{H.new A {H.new 0 {H.new write 1 | move 1 | next A} |
B {H.new write . | move 1 | next H} }
} A H B}
output: zero2one: [0,0,0] -> [1,1,1,.]
{tm add_one
{A.new 1 1 1}
{H.new A {H.new 1 {H.new write 1 | move 1 | next A} |
B {H.new write 1 | move 0 | next B} }
} A B B}
output: add_one: [1,1,1] -> [1,1,1,1]
{tm unary_adder
{A.new 1 1 1 0 1 1 1}
{H.new A {H.new 1 {H.new write 0 | move 1 | next B} } |
B {H.new 1 {H.new write 1 | move 1 | next B} |
0 {H.new write 1 | move 0 | next H} }
} A H B}
output: unary_adder: [1,1,1,0,1,1,1] -> [0,1,1,1,1,1,1]
{tm duplicate
{A.new 1 1 1}
{H.new q0 {H.new 1 {H.new write B | move 1 | next q1} } |
q1 {H.new 1 {H.new write 1 | move 1 | next q1} |
0 {H.new write 0 | move 1 | next q2} |
B {H.new write 0 | move 1 | next q2}} |
q2 {H.new 1 {H.new write 1 | move 1 | next q2} |
B {H.new write 1 | move -1 | next q3}} |
q3 {H.new 1 {H.new write 1 | move -1 | next q3} |
0 {H.new write 0 | move -1 | next q3} |
B {H.new write 1 | move 1 | next q4}} |
q4 {H.new 1 {H.new write B | move 1 | next q1} |
0 {H.new write 0 | move 1 | next qf}}
} q0 qf B}
output: duplicate: [1,1,1] -> [1,1,1,0,1,1,1]
{tm sort
{A.new 2 1 2 2 2 1 1}
{H.new A {H.new 1 {H.new write 1 | move 1 | next A} |
2 {H.new write 3 | move 1 | next B} |
0 {H.new write 0 | move -1 | next E}} |
B {H.new 1 {H.new write 1 | move 1 | next B} |
2 {H.new write 2 | move 1 | next B} |
0 {H.new write 0 | move -1 | next C}} |
C {H.new 1 {H.new write 2 | move -1 | next D} |
2 {H.new write 2 | move -1 | next C} |
3 {H.new write 2 | move -1 | next E}} |
D {H.new 1 {H.new write 1 | move -1 | next D} |
2 {H.new write 2 | move -1 | next D} |
3 {H.new write 1 | move 1 | next A}} |
E {H.new 1 {H.new write 1 | move -1 | next E} |
0 {H.new write 0 | move 1 | next H}}
} A H 0}
output: sort: [2,1,2,2,2,1,1] -> [1,1,1,2,2,2,2,0]
{tm busy_beaver
{A.new}
{H.new A {H.new 0 {H.new write 1 | move 1 | next B} |
1 {H.new write 1 | move -1 | next C}} |
B {H.new 0 {H.new write 1 | move -1 | next A} |
1 {H.new write 1 | move 1 | next B}} |
C {H.new 0 {H.new write 1 | move -1 | next B} |
1 {H.new write 1 | move 0 | next H}}
} A H 0}
output: busy_beaver: [] -> [1,1,1]
{tm busy_beaver2
{A.new}
{H.new A {H.new 0 {H.new write 1 | move 1 | next B} |
1 {H.new write 1 | move -1 | next C}} |
B {H.new 0 {H.new write 1 | move 1 | next C} |
1 {H.new write 1 | move 1 | next B}} |
C {H.new 0 {H.new write 1 | move 1 | next D} |
1 {H.new write 0 | move -1 | next E}} |
D {H.new 0 {H.new write 1 | move -1 | next A} |
1 {H.new write 1 | move -1 | next D}} |
E {H.new 0 {H.new write 1 | move 0 | next K} |
1 {H.new write 0 | move -1 | next A}}
} A K 0}
-> too much recursion
</lang>
=={{header|Lua}}==
| |||