Talk:Universal Turing machine: Difference between revisions
Created page with " == Examples sufficient to find bugs in UTM? == I want to raise the question if the proposed examples (simple incrementer / busy beaver) are enough to find bugs in the code. ..." |
|||
Line 7: | Line 7: | ||
("s0", "a", "s0", "a", right) |
("s0", "a", "s0", "a", right) |
||
("s0", "b", "s1", "B", right) |
("s0", "b", "s1", "B", right) |
||
("s0", "*", "se", "*", left) |
("s0", "*", "se", "*", left) |
||
("s1", "a", "s1", "a", right) |
("s1", "a", "s1", "a", right) |
||
("s1", "b", "s1", "b", right) |
("s1", "b", "s1", "b", right) |
||
("s1", "*", "s2", "*", left) |
("s1", "*", "s2", "*", left) |
||
("s2", "a", "s3", "b", left) |
("s2", "a", "s3", "b", left) |
||
("s2", "b", "s2", "b", left) |
("s2", "b", "s2", "b", left) |
||
("s2", "B", "se", "b", left) |
("s2", "B", "se", "b", left) |
||
("s3", "a", "s3", "a", left) |
("s3", "a", "s3", "a", left) |
||
("s3", "b", "s3", "b", left) |
("s3", "b", "s3", "b", left) |
||
("s3", "B", "s0", "a", right) |
("s3", "B", "s0", "a", right) |
||
("se", "a", "se", "a", left) |
("se", "a", "se", "a", left) |
||
("se", "*", "see", "*", right) |
("se", "*", "see", "*", right) |
||
Example: abbabbabababab => aaaaaabbbbbbbb |
|||
--[[User:Coenig|Coenig]] 14:11, 17 February 2013 (UTC) |
--[[User:Coenig|Coenig]] 14:11, 17 February 2013 (UTC) |
Revision as of 14:13, 17 February 2013
Examples sufficient to find bugs in UTM?
I want to raise the question if the proposed examples (simple incrementer / busy beaver) are enough to find bugs in the code. I have to admit that I uploaded two faulty Java implementations that worked fine with both examples, before I found a (hopefully) correct version. I propose to add this example that helped me fix the bugs:
Sort a tape containing arbitrary sequences of "a" and "b" alphabetically ("*" being blank symbol, "s0" initial state, "see" terminal state):
("s0", "a", "s0", "a", right)
("s0", "b", "s1", "B", right)
("s0", "*", "se", "*", left)
("s1", "a", "s1", "a", right)
("s1", "b", "s1", "b", right)
("s1", "*", "s2", "*", left)
("s2", "a", "s3", "b", left)
("s2", "b", "s2", "b", left)
("s2", "B", "se", "b", left)
("s3", "a", "s3", "a", left)
("s3", "b", "s3", "b", left)
("s3", "B", "s0", "a", right)
("se", "a", "se", "a", left)
("se", "*", "see", "*", right)
Example: abbabbabababab => aaaaaabbbbbbbb
--Coenig 14:11, 17 February 2013 (UTC)