Assuming we have a model of TM with an infinite number of states. The domain and range of the transition function are also infinite. Given a description of a TM $M$ and a string $w$ how can we use the new model to tell if $M$ ever stops when running on $w$?
$\begingroup$
$\endgroup$
2
-
2$\begingroup$ "Given a description of a TM M and a string w, ..." Are you talking about a machine in one of the usual models of TMs or are you talking about a machine in the new model? $\endgroup$– John L.Jan 20, 2019 at 17:20
-
1$\begingroup$ In the usual models $\endgroup$– idanJan 22, 2019 at 13:06
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
6
If you are allowed infinite states and transition functions, then even a DFA could solve the halting problem (and in fact, any language). In this case, the DFA/TM can basically have a state for each possible pair of TM + word. If a certain state represents a pair where the TM halts on the word it would be an accepting state.
Notice that I don't give a constructive algorithm of how to build this TM/DFA, but it could easily be seen that such a TM theoretically exists and therefore decides the halting problem.
EDIT - more detail regarding the last point: by definition, a language is regular if there exists some DFA accepting it, even if we don't know how to build that DFA. If we allow infinite states, than all languages will be regular. The infinite-state-DFA I described above may seem confusing because we have no idea how to construct it, and in particular, how to choose which states are accepting and which aren't. However, it definitely still exists!
Another way to think about it is that the states of the DFA can be computed/built in "compile-time" and therefore we don't need to figure out whether a TM stops on a word in "run time". We determine what is accepting and what isn't before we even get any input, and when we do get an input, we will definitely halt on it because of the nature of DFAs. We don't need to simulate a TM on an input during the DFAs run!
Lastly, I want to emphasize that the confusion regarding DFAs which we have no algorithm to construct is valid even using the standard, finite-state model of DFAs. If we denote the halting problem by $H_{TM}$, then for all $n$, the language $H_n:=H_{TM}\cap \{0,1\}^n$ is a finite language and therefore regular! However, it can be proved that there is no general algorithm that takes $n$ as an input constructs a DFA for $H_n$, since otherwise we could decide the halting problem.
-
$\begingroup$ Thanks. I thought counting the number of times we go right on Ms input tape, assum this number is $r$, So all possible different configurations of M on w is $|Q|*r*|\Gamma|^r$. Now, we have infinite number of states , so let the new TM have $|Q|*r*|\Gamma|^r$ states..one for each configuration. Now we can tell if M stops on w and accepts or not. $\endgroup$– idanJan 20, 2019 at 16:57
-
$\begingroup$ We can take as many states as we need so we can do this. $\endgroup$– idanJan 20, 2019 at 17:03
-
$\begingroup$ I think it won't work since $M$ might go right an infinite number of times, and therefore the "counting" part of the algorithm might never end. $\endgroup$ Jan 20, 2019 at 17:33
-
$\begingroup$ You wrote "If a certain state represents a pair where the TM halts on the word.. " But how can I know if some M halts on some w ? I need to simulate M on w. $\endgroup$– idanJan 22, 2019 at 13:11
-
1