Universal Turing machine: Difference between revisions
Content added Content deleted
(→{{header|Java}}: Example sorting included.) |
(→Tcl: Added implementation) |
||
Line 1,222: | Line 1,222: | ||
[]) # starting tape |
[]) # starting tape |
||
print t.run, "\n"</lang> |
print t.run, "\n"</lang> |
||
=={{header|Tcl}}== |
|||
<lang tcl>proc turing {states initial terminating symbols blank tape rules {doTrace 1}} { |
|||
set state $initial |
|||
set idx 0 |
|||
set tape [split $tape ""] |
|||
if {[llength $tape] == 0} { |
|||
set tape [list $blank] |
|||
} |
|||
foreach rule $rules { |
|||
lassign $rule state0 sym0 sym1 move state1 |
|||
set R($state0,$sym0) [list $sym1 $move $state1] |
|||
} |
|||
while {$state ni $terminating} { |
|||
set sym [lindex $tape $idx] |
|||
lassign $R($state,$sym) sym1 move state1 |
|||
if {$doTrace} { |
|||
### Print the state, great for debugging |
|||
puts "[join $tape ""]\t$state->$state1" |
|||
puts "[string repeat { } $idx]^" |
|||
} |
|||
lset tape $idx $sym1 |
|||
switch $move { |
|||
left { |
|||
if {[incr idx -1] < 0} { |
|||
set idx 0 |
|||
set tape [concat [list $blank] $tape] |
|||
} |
|||
} |
|||
right { |
|||
if {[incr idx] == [llength $tape]} { |
|||
lappend tape $blank |
|||
} |
|||
} |
|||
} |
|||
set state $state1 |
|||
} |
|||
return [join $tape ""] |
|||
}</lang> |
|||
Demonstrating: |
|||
<lang tcl>puts "Simple incrementer" |
|||
puts TAPE=[turing {q0 qf} q0 qf {1 B} B "111" { |
|||
{q0 1 1 right q0} |
|||
{q0 B 1 stay qf} |
|||
}] |
|||
puts "Three-state busy beaver" |
|||
puts TAPE=[turing {a b c halt} a halt {0 1} 0 "" { |
|||
{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} |
|||
}] |
|||
puts "Sorting stress test" |
|||
# We suppress the trace output for this so as to keep the output short |
|||
puts TAPE=[turing {A B C D E H} A H {0 1 2 3} 0 "12212212121212" { |
|||
{A 1 1 right A} |
|||
{A 2 3 right B} |
|||
{A 0 0 left E} |
|||
{B 1 1 right B} |
|||
{B 2 2 right B} |
|||
{B 0 0 left C} |
|||
{C 1 2 left D} |
|||
{C 2 2 left C} |
|||
{C 3 2 left E} |
|||
{D 1 1 left D} |
|||
{D 2 2 left D} |
|||
{D 3 1 right A} |
|||
{E 1 1 left E} |
|||
{E 0 0 right H} |
|||
} no]</lang> |
|||
{{out}} |
|||
<pre> |
|||
Simple incrementer |
|||
111 q0->q0 |
|||
^ |
|||
111 q0->q0 |
|||
^ |
|||
111 q0->q0 |
|||
^ |
|||
111B q0->qf |
|||
^ |
|||
TAPE=1111 |
|||
Three-state busy beaver |
|||
0 a->b |
|||
^ |
|||
10 b->a |
|||
^ |
|||
11 a->c |
|||
^ |
|||
011 c->b |
|||
^ |
|||
0111 b->a |
|||
^ |
|||
01111 a->b |
|||
^ |
|||
11111 b->b |
|||
^ |
|||
11111 b->b |
|||
^ |
|||
11111 b->b |
|||
^ |
|||
11111 b->b |
|||
^ |
|||
111110 b->a |
|||
^ |
|||
111111 a->c |
|||
^ |
|||
111111 c->halt |
|||
^ |
|||
TAPE=111111 |
|||
Sorting stress test |
|||
TAPE=0111111222222220 |
|||
</pre> |