1
$\begingroup$

This question is about the (Edit: universal) Halting Problem on a TM with finite space.

The Halting Problem is obviously decidable on those TMs. So my question now is how efficient we can decide it.

My intuition is, that there is now better way than brute force. Because, if we have a better algorithm than that (for an arbitrary TM with arbitrary much but limited space) we would have a better algorithm for the Halting Problem on any TM. (And I guess that such a strategy can not exist on the general problem)

But how can we prove this?

$\endgroup$
2
  • 1
    $\begingroup$ What do you mean by brute force here? Do you mean simulating the execution of the TM with the given input $w$? $\endgroup$
    – Russel
    Commented Dec 2, 2022 at 10:35
  • $\begingroup$ I'm talking about the "does the TM halt on any input" halting problem. So brute force would be trying any input. $\endgroup$
    – Ondolin
    Commented Dec 2, 2022 at 12:00

1 Answer 1

2
$\begingroup$

Consider a Turing machine with alphabet $\Sigma$, states $Q$, a transition function $\delta$ and a tape with $k$ cells.

The configurations of this Turing machine (contents of the tape, current state, position of the read-write head) form a finite set $\Sigma ^k \times Q \times [k-1]$ if $[k-1] = \{n \in \mathbb N : n \lt k\}$ representing an index for the position of the read-write head.

Consider the directed graph where the nodes $m_i$ are elements from $(\Sigma^k \times Q \times [k-1])$ and there is an edge between two nodes $m_i$ and $m_j$ if $(m_i, m_j) \in \delta$.

Look at the starting configuration. The question of whether this Turing machine halts is can be interpreted as whether the starting configuration has a path to a cycle or whether there is a path from the starting configuration to the halting state.

Both of these questions can be answered using a search algorithm in $O(|V| + |E|)$ time.

If the alphabet has $n = |\Sigma|$ elements and the Turing machine has $s=|Q|$ different states then the graph has $kn^ks$ nodes.

If the Turing machine is deterministic then the graph has one edge for every non-terminal state.

If the Turing machine is non-deterministic then there is an upper bound of $O((kn^ks)^2)$ edges.

So for deterministic Turing machines, you can solve the problem in $O(kn^ks)$ time and in $O((kn^ks)^2)$ time for non-deterministic Turing machines.

$\endgroup$
4
  • $\begingroup$ Ok, I get that idea. First of all to the whether the starting configuration is part of a cycle part: it should be whether there is a path to a node which is part of a cycle. The other problem is, that this approach only works on the empty word. $\endgroup$
    – Ondolin
    Commented Dec 2, 2022 at 12:15
  • $\begingroup$ it should be whether there is a path to a node which is part of a cycle This is correct. This approach only works on the empty word The general method remains the same. You can either choose the starting configuration as a node that has the tape equal to the input or add an additional element to the configuration to denote the value of the input, you can re-calculate the number of nodes and edges for the resulting new graph. @Ondolin $\endgroup$
    – Sam Ezeh
    Commented Dec 2, 2022 at 12:27
  • $\begingroup$ That’s true. But that’s just a brute force approach. And by the way, you don’t need the graph. Simply running it will have the same runtime. $\endgroup$
    – Ondolin
    Commented Dec 2, 2022 at 14:37
  • $\begingroup$ Wouldn't doing it faster by another method imply a faster solution to the corresponding graph problem? You can also view the tape-restricted Turing machine as describing a Deterministic Finite Automaton, you're deciding the same question for the corresponding DFA. @Ondolin $\endgroup$
    – Sam Ezeh
    Commented Dec 2, 2022 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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