In a Turing machine, can we determine how many times a loop will be processed?

268 Views Asked by At

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?

1

There are 1 best solutions below

0
On

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.