patternMinor
Counters in Turing machines
Viewed 0 times
turingcountersmachines
Problem
I know how a Turing machine works, how it accepts a language but in some.
In some scenarios we would like to use counters.
For example, I want to develop a machine that accepts $\{0^{2n} : n \geq 0\}$. How can I count the number of zeroes?
If some one of you could solve the following problem for me it would help my understanding of these matters:
Design a Turing machine for $L = \{1^{3^n} : n \geq 1\}$.
In some scenarios we would like to use counters.
For example, I want to develop a machine that accepts $\{0^{2n} : n \geq 0\}$. How can I count the number of zeroes?
If some one of you could solve the following problem for me it would help my understanding of these matters:
Design a Turing machine for $L = \{1^{3^n} : n \geq 1\}$.
Solution
Well, you could just implement a counter. I'll assume that the tape alphabet is $\{0,1,\#\}$.
First, scan to the end of the input, and write $\#0$ to the tape after the last character. The string of zeroes and ones after the $\#$ will be a binary counter.
Second, convince yourself that a Turing machine can add one to a number in binary.
Third, peform the following until you run out of input. Scan back to the first $1$ on the tape, replace it with a $\#$, scan back to the counter and add one to it.
Finally, when you've run out of input, check that the value of the counter is a number of the required type. For example, it has the value $2^k$ for some $k$ precisely if it matches the regular expression $10^*$. For $3^k$, you can either convince yourself that Turing machines can divide a binary number by $3$ or – easier! – keep your counter in ternary instead of binary.
First, scan to the end of the input, and write $\#0$ to the tape after the last character. The string of zeroes and ones after the $\#$ will be a binary counter.
Second, convince yourself that a Turing machine can add one to a number in binary.
Third, peform the following until you run out of input. Scan back to the first $1$ on the tape, replace it with a $\#$, scan back to the counter and add one to it.
Finally, when you've run out of input, check that the value of the counter is a number of the required type. For example, it has the value $2^k$ for some $k$ precisely if it matches the regular expression $10^*$. For $3^k$, you can either convince yourself that Turing machines can divide a binary number by $3$ or – easier! – keep your counter in ternary instead of binary.
Context
StackExchange Computer Science Q#65886, answer score: 2
Revisions (0)
No revisions yet.