computer scienceturing-machines
Design a Turing Machine which accepts word with odd length with one in the middle
for example : $00100\in L,\quad 011\in L$ but $101,11,11011\notin L$
I tried this:
delete the first digit(deleted digit marked with x) and then go right till you see a space, when you walk on the first space (the end of the word) delete the first digit from the right (marked with y) then go left till you see x (loop)
any ideas?
The problem with your original proof is that strings are by definition finite in the context of formal languages, though languages can be infinite... If you decide to go the route of a reduction then take care that your reduction is 1) the right way, 2) has any closure properties you are looking for: eg. many-to-one vs. turing wrt. closure by complementation, 3) is truly a reduction in that solutions for A must exist iff (pay attention to the inner iff) solutions exist on the other side of the reduction $$ A \leq_m B \iff \exists f \in rec :(x \in A \iff f(x) \in B).$$
Bit of a spoiler, but sounds like a good candidate for Rice's Theorem:
Let $P$ be a property of languages over $\Sigma = \{0,1\}^*$ such that $P \neq \emptyset$ and $P \neq \Sigma^*$. Then $$ X = \{ <M> | M \text{ is a TM that decides a language with property}\; P \} $$ is undecidable.
First, let's start with a high level description of such a machine. Abstractly, we want to scan to the right across the tape, and test when we've passed from one block into the next. More concretely, we want to count how many spaces we've passed (since spaces are the dividing symbols between blocks). Once we've passed one space, we're going into the second block of strokes; after two spaces, we're going into the third block.
Next, we'll describe the state transition function for our first machine:
From the initial state $q_0$, if the symbol under the tape head is a stroke, move right (without writing to the tape, of course), and stay in the same state. If the symbol is a space, move right and halt (then the tape head will stop directly on the first stroke of the second block). If the symbol is a blank, we have an error.
The precise, low-level definition of the Turing machine now depends on your exact definition. For definiteness, I'll use this definition (Source: http://en.wikipedia.org/wiki/Turing_machine#Formal_definition, paraphrased slightly):
A Turing Machine is a 7-tuple $M = (Q, \Gamma, b, \Sigma, q_0, F, \delta)$, where:
- $Q$ is a finite, nonempty set (the state set),
- $\Gamma$ is a finite, nonempty set (the tape alphabet),
- $b \in \Gamma$ is the blank symbol,
- $\Sigma \subseteq \Gamma \setminus \{b\}$ is the input alphabet,
- $q_0 \in Q$ is the initial state,
- $\varnothing \ne F \subseteq Q$ is the set of final (halting) states, and
- $\delta: (Q \setminus F) \times \Gamma \to Q \times \Gamma \times \{L,R\}$ is the state transition function.
We'll do the easy ones first: The tape alphabet $\Gamma$ consists of three symbols, $\Gamma = \{ b, /, \_\}$, where $b$ is the blank symbol, $/$ is the stroke, and $\_$ is the space. $\Sigma = \{ /, \_ \}$ is our input alphabet.
Our state set $Q$ has three elements, say $Q = \{q_0, q_\textrm{HALT}, q_\textrm{ERR}\}$, where $q_0$ is the initial state and $F = \{q_\textrm{HALT}, q_\textrm{ERR}\}$ are the halting states. So, all that's left is to define $\delta$, which we'll do as follows:
$$\begin{align} \delta(q_0, /) &= (q_0, /, R) \\ \delta(q_0, \_) &= (q_\textrm{HALT}, \_, R) \\ \delta(q_0, b) &= (q_\textrm{ERR}, b, R) \\ \end{align}$$
This completes the low-level definition of the first machine.
For the second machine, we need a little bit more complexity. This time, we want to scan right until we find the first space, remember that we've seen it, then scan right again to the second space, and stop on the next stroke. Remember that a Turing machine has only two ways of "remembering" anything: either on the tape, or in its state. Since we aren't allowed to write to the tape, we'll use state. In particular, we'll use two non-final states this time. Our initial state $q_0$ will scan right as before, but once it finds a space, it will transition to state $q_1$ instead. Then, $q_1$ will scan right in the same way until it finds a space; once it finds a space, $q_1$ will transition to $q_\textrm{HALT}$.
Formally, replace $Q$ above by $Q' = \{q_0, q_1, q_\textrm{HALT}, q_\textrm{ERR}\}$, and replace $\delta$ above by $\delta'$ defined as follows:
$$\begin{align} \delta'(q_0, /) &= (q_0, /, R) \\ \delta'(q_0, \_) &= (q_1, \_, R) \\ \delta'(q_0, b) &= (q_\textrm{ERR}, b, R) \\ \\ \delta'(q_1, /) &= (q_1, /, R) \\ \delta'(q_1, \_) &= (q_\textrm{HALT}, \_, R) \\ \delta'(q_1, b) &= (q_\textrm{ERR}, b, R) \end{align}$$
Note that usually, we just give a high-level description of a Turing machine, since that whole low-level description is hard to write, hard to read, and not very enlightening. But, especially when first studying the subject, it's important to keep in mind what the low-level machine actually looks like.
Here are graphical representations of the two machines:
Best Answer
Your strategy of replacing with x's on the left and y's on the right is fine, but at some point you need to check for that 1 in the middle (and oddness).
So: when you get back to q0 coming from q3, and you see a y, then you must have had an even length string, so then you should reject.
Also: coming from q0: if you see a 0 you should go to a different state than if you see a 1, because that 0 or 1 could be the middle symbol. So: if after replacing that 0 or 1 with an x, and you see a y (or a space, in case your string was just a single symbol) to the right of it, then you should stop, and accept or reject depending whether you just replaced a 1 or 0 (this is why you need two different states.
Here is an updated machine: