I'm writing a transition diagram for a Turing Machine which will compute Stretch(y+1). the output consists of the string that replaces each input letter with y copies of that input character. Is it possible to have y as a variable in my diagram and do a loop which will execute y times?
Asked
Active
Viewed 267 times
1 Answers
0
No. That's the thing with Turing-machines: variables (well, the value they have) are represented on the tape, and you since you cannot anticipate the value that the variable takes on, you cannot use some piece of Turing-machine code that executes some loop some predetermined number of times in accordance to that variable.
Bram28
- 100,612
- 6
- 70
- 118