Constructive proof of decidability of finite Halting-problem-style set that does not use table lookup - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-08-22T07:50:45Z https://cs.stackexchange.com/feeds/question/44458 http://www.creativecommons.org/licenses/by-sa/3.0/rdf https://cs.stackexchange.com/q/44458 7 Constructive proof of decidability of finite Halting-problem-style set that does not use table lookup scifie https://cs.stackexchange.com/users/35564 2015-07-16T13:28:00Z 2015-07-17T20:44:46Z <p>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}\}$</p> <p>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)?</p> https://cs.stackexchange.com/questions/44458/-/44475#44475 10 Answer by babou for Constructive proof of decidability of finite Halting-problem-style set that does not use table lookup babou https://cs.stackexchange.com/users/8321 2015-07-16T22:48:24Z 2015-07-16T22:48:24Z <h2>There is no general way to find a decider TM for $L_k$</h2> <p>You are correct that $L_k$ is recursive because, being a subset of the finite set $\Sigma^k$, it is also finite.</p> <p>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.</p> <p>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.</p> <p>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.</p> <p>So the procedure $\mathcal P$ cannot exist.</p> <p>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$.</p> <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.</p> https://cs.stackexchange.com/questions/44458/-/44483#44483 4 Answer by Raphael for Constructive proof of decidability of finite Halting-problem-style set that does not use table lookup Raphael https://cs.stackexchange.com/users/98 2015-07-17T06:06:11Z 2015-07-17T07:32:30Z <p>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.</p> <p>Case in point, there are <a href="https://en.wikipedia.org/wiki/Universal_Turing_machine" rel="nofollow"><em>universal Turing machines</em></a>, that is finitely described TMs that can exhibit <em>any</em> behaviour, from terminating quickly over running arbitrarily long to looping, given the right input.</p> <p>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.</p> <p>More specifically, you ignore the <em>input</em> of the encoded TM, which can be arbitrarily large (and convoluted). The actual state of a TM is the product of control state <em>and</em> 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.</p> https://cs.stackexchange.com/questions/44458/-/44484#44484 6 Answer by Yuval Filmus for Constructive proof of decidability of finite Halting-problem-style set that does not use table lookup Yuval Filmus https://cs.stackexchange.com/users/683 2015-07-17T07:19:20Z 2015-07-17T07:19:20Z <p>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.</p> <p>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 &gt; f(k)$ for infinitely many $k$. Roughly speaking, $B_k$ grows faster than every computable function.</p> <p>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 &gt; f(k)$ for <em>all</em> $k \geq K$. This was first proved by <a href="http://computation4cognitivescientists.weebly.com/uploads/6/2/8/3/6283774/rado-on_non-computable_functions.pdf">Rado</a>.</p> <hr>