Can someone help me with some tips on how to create a turing machine that only accepts even length strings with an input alphabet of {0,1}?
[Math] Turing machine that accepts even length strings
discrete mathematicsturing-machines
Related Solutions
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.
$R$ is a known Turing machine, so we don't have to use the universal Turing machine. We just switch to running $R$ on the input $\langle S_{M, w} \rangle$. We "call $R$ as a helper function", to use a programming analogy.
The idea is that $T$ decides halting problem. We know that $T$ always halts, since by assumption $R$ always halts.
Now note that $R$ accepts $\langle S_{M, w} \rangle$ iff $L(S_{M, w}) \neq \emptyset$ iff $\{0 | M$ halts on $w\} \neq \emptyset$ iff $M$ halts on $w$.
And note that $T$ accepts $\langle M, w \rangle$ iff $R$ accepts $S_{M, w}$ iff $M$ halts on $w$. So $T$ solves the halting problem.
But we know the Halting problem cannot be decided by any Turing machine. This is a contradiction.
Edit for more detail on "simulation":
Consider two Turing machines $T_1$ and $T_2$. We can "compose" the two machines to produce a machine $T$ which does the following:
- Run $T_1$ on the input.
- Run $T_2$ on whatever is left on the tape from the execution of $T_1$. If $T_2$ is an accepting/rejecting machine rather than just a machine which computes an output on the tape, then accept/reject as $T_2$ does.
The idea is as follows: our combined machine will have all the states which $T_1$ has, together with all the states $T_2$ has (WLOG assuming no overlap). The starting state will be the initial state of $T_1$. When we reach a halting state of $T_1$, instead of halting, we transition to the starting state of $T_2$.
We call $T$ the "composition" $T_2 \circ T_1$ because if $T_1$ computes function $f_1$ and $T_2$ computes function $f_2$, $T$ will compute $f_2 \circ f_1$.
Recall the steps given in the text:
- From $\langle M, w \rangle$ construct $\langle S_{M, w} \rangle$.
- Execute $R$ on the input $\langle S_{M, w} \rangle$. Accept iff $R$ accepts; reject iff $R$ rejects.
This is the composition of two Turing machines. Let $T_1$ be the Turing machine which computes $\langle S_{M, w} \rangle$ from $\langle M, w \rangle$. Then the Turing machine we want to construct is $T = R \circ T_1$.
Best Answer
Suppose you start from the leftmost 1. You need a "status bit" saying if the number of 1's counted so far is even/odd. In each step, change the status bit and move right until the symbol is 0.