Given a single taped deterministic turing machine what's the least amount of calculations needed in order to receive the language

Question

Given a single taped deterministic turing machine what's the least amount of calculations needed in order to receive the language $L_k=${$0,1$}$^*0${$0,1$}$^{k-1}$.

My intuition says that i'll need at least $n+k$ calculations.

I will start at the leftmost digit, and go through whole the tape until i reach blank on the rightmost corner of the tape.

Then i'll create {$\sigma_1,...\sigma_{k-1}$} new alphabets in order to the 'count' the digits, Once i'm done using $\sigma_{k-1}$ digits i know i should reach $0$, If i don't i reject.

The solution above has 2 problem:

Since {$0,1$}$^*$ can be infinite, The machine above will never reach accept state.
I'm not sure it's the most efficent way.

Help please.

I assume you mean letters rather than alphabets? You can do it in $n$ steps if you allow $O(2^k)$ states. — Thomas Andrews, Dec 30 '13 at 22:59
As for objection (1), ${0,1}^*$ cannot be infinite. It is unbounded, but it doesn't match any infinite string. — Thomas Andrews, Dec 30 '13 at 23:01

Thomas Andrews · Accepted Answer · 2013-12-31T00:35:59.880

2

You only need to remember the last $k$ digits in the state. You also have to deal with the states before you get to $k$ digits. Then when you get the the vacant entry on the strip, the process halts, and either succeeds or fails based on the state - which encodes the last $k$ bits. This actually requires a Turing machine with $2^{k+1}$ states, including the final state and the preliminary states.

For example, if $k=2$, you'd have the following states:

$$e,0,1,00,01,10,11,f$$

edited Dec 31 '13 at 00:35

answered Dec 30 '13 at 23:33

Thomas Andrews

177,126

1

Assume $k=2$ and we input $110101$. I guess, it starts on state $e$, but when will it pass to state '0'? At the first or second zero? It feels like it's rather a nondeterministic machine.. – Berci Dec 31 '13 at 00:40
2

The states with that input are: $e\to 1\to 11\to 10\to 01\to 10\to 01\to f$. The last step, when we read the "empty" cell, indicates success. If you got an empty cell in states $00$ or $01$ then you'd succeed, otherwise, you'd fail. – Thomas Andrews Dec 31 '13 at 00:45
1

In particular, it will never be in state $0$. – Thomas Andrews Dec 31 '13 at 00:46
I don't get it yet. I need to create $2^{k-1}$ states in order to remember the different permutations of: {$0,1$}$^{k-1}$. How do i actually 'deal' with the states before the last $k$ digits? How can i use the remembered permutations in my favour? – StationaryTraveller Dec 31 '13 at 09:34
1

A Turing machine is a set of states and a set of actions given the states and the contents of the current cell. If your state is $01$ at some point, and you next read $1$, then you move to state $11$ and move the head to the right. If you next read $0$, your state changes to $10$ and you move the head to the right. If your head is empty, then the last two digits are $01$, and you've got a match, because $0$ is the first digit of $01$. – Thomas Andrews Dec 31 '13 at 23:27
Got it, Thanks. Really clever solution. – StationaryTraveller Jan 01 '14 at 11:19

Given a single taped deterministic turing machine what's the least amount of calculations needed in order to receive the language

1 Answers1