Turing machine - compare two words

Question

I have a simple turing machine with single tape. I need to compare two words <w1>$<w2>$ and write output. Language is all letters and numbers.

I did comparation with the {a,b} language but there are more characters.

Is only solution do it one by one in different branches? I mean read / mark the letter (enter the letter branch), go to the second word and read /mark the same letter, go to the first word, repeat? My problem with this solution is, when I want to change something I need to remake all branches. The other problems are the error handling, when I do not find the right letter I don't want crash. How handle that?

Answer 1

Yes, running back and forth comparing letters is the best you can do. You could always read and remember two, three or any fixed amount of symbols at a time; then there would be less running back and forth, but the programming would be even worse.

And yes, in general you have to rewrite everything when you change something. There are no functions, procedures etc. that you can program in a modular way. In principle, though, you could use different, disjoint sets of states in different parts of your computation. If you change something in one part, you only need to adapt the "interface" where you move from one set of states to another.

If you do not find the right letter, in principle there is no problem with "crashing", because this probably means not accepting. If you want a "controlled" end, you can for example run to the right end of the input and stop there (stopping means entering a configuration where no more move is possible); if this kind of stopping for you is "crashing" you can also enter into an infinite loop.