7
$\begingroup$

I tried to prove that the following language is recursive: for $\Sigma=\{0,1\}$, $k$ a positive integer: $$ L_k= H_{\mathrm{TM},\varepsilon}\cap \Sigma^k $$ where $H_{\mathrm{TM},\varepsilon}=\{\langle M\rangle\mid M \text{ is a TM that halts on an empty input}\}$

It is easy to prove because $L_k$ is finite, but I didn't notice this and tried to prove it by finding a decider TM for it. I thought that since the encoding of the TM is of length $k$ then it can't have more than $2^k$ states, and by running it on epsilon for $2^k$ steps, if it halts by then than accept otherwise reject. I was told that it's incorrect - is it a wrong solution. How can I prove this using this method (and not the way I mentioned about $L_k$ being finite)?

| cite | improve this question | |
$\endgroup$
  • 3
    $\begingroup$ I took the liberty of editing your post into LaTex form. If I've misread your intent, please feel free to revert it to your original form. I've also suggested that it be reopened. Let's see how that goes. By the way, welcome to the site. $\endgroup$ – Rick Decker Jul 16 '15 at 18:07
  • $\begingroup$ Since $H_{\mathrm{TM},\varepsilon}$ is undecidable, it can not be represented by a recursively-enumerable union of decidable sets. Hence, there are undecidable infinite (and co-infinite) subsets of $H_{\mathrm{TM},\varepsilon}$. Therefore, you have to use finiteness in some way. You are asking, "how do I show decidability using finiteness in a less obvious way?". I'm not sure in which sense that is a helpful question for you. $\endgroup$ – Raphael♦ Jul 17 '15 at 5:57
  • $\begingroup$ @Raphael: $H_{\mathrm{TM},\epsilon}$ is the union of the sets $\{\langle M\rangle \mid M \text{ is aTM that halts within } t \text{ steps on $\epsilon$ input}\}$ for positive integers $t$. Therefore $H_{\mathrm{TM},\epsilon}$ is "a recursively-enumerable union of decidable sets." $\endgroup$ – user12859 Jul 17 '15 at 8:22
  • $\begingroup$ @RickyDemer True, thanks. My argument works only for non-semi-decidability (does it?). $\endgroup$ – Raphael♦ Jul 17 '15 at 9:19
10
$\begingroup$

There is no general way to find a decider TM for $L_k$

You are correct that $L_k$ is recursive because, being a subset of the finite set $\Sigma^k$, it is also finite.

You would like to rather find a decider TM for $L_k$, and you suggest some techniques. Without even going into the details of these techniques and why they do not work, you do not stand any chance of ever succeeding.

The first thing you should notice is that the finiteness argument tells you that there exists a decider TM $M_k$ for the language $L_k$, but it does not tell you what this TM is. It is an example of a non-constructive proof: you prove that a decider exists, but you cannot tell which it is.

Now, suppose that, given $k$, you have a procedure $\mathcal P(k)$ to find such a decider $M_k$ for the language $L_k$ (rather than just prove it exist). Then, given any Turing machine $M$, then there is an integer $k'$ such that $|\langle M\rangle|=k'$, so that $\langle M\rangle\in \Sigma^{k'}$. Then you can use the procedure $\mathcal P$ to find a decider TM $M_{k'}$ that can determine whether $\langle M\rangle\in L_{k'}$. So you have a way to decide whether the TM $M$ halts on empty input. And this works for any TM $M$. However, this is not possible, because it is undecidable whether a given TM $M$ halts on empty input.

So the procedure $\mathcal P$ cannot exist.

Since you are looking for a general way to find the decider TM $M_{k'}$, you cannot succeed because that method would be precisely a procedure such as $\mathcal P$.

Note that this proof could still leave the (very remote) possibility of finding a decider for some specific values of $k$, but you would have to identify precisely the concerned values, and the method would not work for all values of $k$. I am not advising you to try.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ So basically the only way to prive it is recursive is to use the finitness argument? $\endgroup$ – jon Prime Jul 16 '15 at 22:53
  • $\begingroup$ I tried to prove it this way due to the face that I probably didn't understand very well when to use such arguments about the number of possible configurations and states: for example the question of proving that L100 = {<M> | M on epsilon does not use more than 100 places on the tape} is recursive is proved by running the TM for |Q|·100 · |Gama|^100 +1 steps. So can someone please explain when such arguments are appropriate - in what types of questions, maybe a few examples of when such arguments can be used and when they can't? $\endgroup$ – jon Prime Jul 16 '15 at 23:01
  • 3
    $\begingroup$ I guess one can never say there is only one way to prove a result. All I can say is that any proof that works for all values of $k$ will necessarily be a non-constructive proof, that will not tell you what the decider TM is. $\endgroup$ – babou Jul 16 '15 at 23:10
  • 2
    $\begingroup$ Regarding your attempt, it is a bit confused. The size of ⟨M⟩ is just like the size of a program text. It is unrelated to how much memory the program will actually use. For TM, it is actually the description of the TM in a very abstract sense, so that a very short description can correspond to a extremely complex TM. The size $k$ does not tell you how much memory is used. Arguments based on the size of the memory are more complex (exponential number of configurations), and do require the memory to be bounded in size, which is not the case here. $\endgroup$ – babou Jul 16 '15 at 23:28
  • $\begingroup$ A general constructive proof does not have to induce a computable (!) procedure $\mathcal{P}$. For instance, the canonical proof is constructive, in a way: table-lookup, i.e. hard-code the result for all inputs in $L_k$. Of course, there can be no algorithm for constructing this table (for infinitely all $k$) for the reasons you mention. $\endgroup$ – Raphael♦ Jul 17 '15 at 6:00
6
$\begingroup$

You can "fix" your proof using the busy beaver function. Let $B_k$ be the maximal number of steps that a Turing machine of description size at most $k$ performs before halting, when given the empty input. If you know $B_k$ (or even just an upper bound on $B_k$, that is, some $T_k \geq B_k$) then you can solve the halting problems for Turing machines of description size $k$ (and the empty input) by running the given machine for up to $B_k$ (or $T_k$) steps. If it doesn't halt by that point, then you know that it never halts.

Since the halting problem isn't decidable, we know that the function $B_k$ cannot be computable. Indeed, no computable function $T_k$ satisfies $T_k \geq B_k$ for all $k$. In other words, for any computable function $f(k)$, it is the case that $B_k > f(k)$ for infinitely many $k$. Roughly speaking, $B_k$ grows faster than every computable function.

In fact, using diagonalization one can show that $B_k$ does grow faster than every computable function: for every computable $f(k)$ there exists $K$ such that $B_k > f(k)$ for all $k \geq K$. This was first proved by Rado.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Finding the maximum number of steps s TM of size can take before definitely going into a loop is exactly what I was tiring to prove - I wanted to argue that since a the TM is of size K, than the maximum number of states it can have encoded is 2^k and my logic was (and tell me if I am wrong) - if on a certain input a TM with m states makes at least m+1 moves (ie repeats a state) it will definitely loop. $\endgroup$ – scifie Jul 24 '15 at 22:03
  • $\begingroup$ And regarding your suggestion of finding the maximal number of steps that a Turing machine of description size at most k performs before halting, isn't than number supposed to be 2^k like I suggested? $\endgroup$ – scifie Jul 24 '15 at 22:04
  • $\begingroup$ Unfortunately you are wrong. What you write is true for finite automata but not for Turing machines, whose state includes a tape. Take it as an exercise to construct a Turing machine with $n$ states that halts after $2^{2^n}$ steps (roughly). $\endgroup$ – Yuval Filmus Jul 24 '15 at 22:10
  • $\begingroup$ @ Yuval Filmus, that's incorrect - TM's states aren't related to the Tape. TMs states are denoted by Q and it's a finite set. How is it connected to its Tape? The tape is for input manipulation and isn't part of the States of a TM. $\endgroup$ – scifie Jul 25 '15 at 22:53
  • $\begingroup$ @scifie The state includes everything you need to describe the current situation the machine is in. This includes the state proper (what you refer to), the location of the head, and the contents of the tape. $\endgroup$ – Yuval Filmus Jul 25 '15 at 22:58
4
$\begingroup$

The core fallacy is that you assume that the number of states a TM has limits its runtime (before termination) in some way. This is false.

Case in point, there are universal Turing machines, that is finitely described TMs that can exhibit any behaviour, from terminating quickly over running arbitrarily long to looping, given the right input.

On a technical note, universal TMs are usually described as taking two parameters, one TM encoding and the input to simulate it on. It is easy to merge them into one parameter, so there are indeed unary universal TMs.

More specifically, you ignore the input of the encoded TM, which can be arbitrarily large (and convoluted). The actual state of a TM is the product of control state and tape content, so a simple combinatorial argument based on the number of control states alone is not sufficient. In particular, a TM is not in an unescapable loop when it visits some state for the second time.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Heh, turns out my answer does not apply here, since we only consider a fixed (empty) input. The runtime is limited in this case, cf. Yuval's answer. $\endgroup$ – Raphael♦ Jul 17 '15 at 7:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.