Talk:Universal Turing machine

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): <lang java>("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)</lang>

Example: abbabbabababab => aaaaaabbbbbbbb

--Coenig 14:11, 17 February 2013 (UTC)

We get: 0111111222222220. The blanks on both ends seem to be in the rules, don't you get them? Unless I'm not reading it correctly: the very last rule, for instance, writes a blank just before he goes to the halting position, so it has to be part of the output.Fwend 20:36, 17 February 2013 (UTC)

I don't think that you understood my TM definition correctly (or I'm wrong in understanding what you mean). I used a different notation than on the main site. In my TM s1, s2, ... are the states, a, b are the tape symbols, and * is the blank symbol.

Then, ("s1", "a", "se", "b", left) means that we read a on the tape, switch from state s1 to state se, write b on the tape and move to the left. 0, 1, 2 are not tape symbols. You are right, thogh, that the tape looks something like this in the end: **aaaaaabbbbbbbb** --Coenig 07:36, 19 February 2013 (UTC)

In the D implementation, we use different symbols, but the output is the same. Fwend 16:16, 19 February 2013 (UTC)