Let $A(n, B, d)$, $B(n, d)$ be a {Turing machine, random-access machine, C program} with finite tape (which I'm going to denote "Turing machine*" and "random-access machine*" respectively), $n \in \mathbb{N}$. $A$ and $B$ are the same type of machine. For any $N \in \mathbb{N}$, statements where $n \leq N$, don't matter.

$n + |d|$ is the number of spatial units on $B$'s tape if $B$ is a Turing machine* or random-access machine*. If it is a C program, $n$ is the number of Bytes in $B$'s read-write memory (registers are neglected, see last sentence of previous pragraph). The memory $d$ takes up is read-only and not accounted for. All spatial units regarded are capable of holding the same amount of information.

$d$ is the argument data. You may assume $n$ to be included in $d$.

If $A$ is a Turing machine* or random-access machine*, it may access $2 \cdot (n + |d|) + c$ spatial units where $c$ is constant.

If $A$ is a C program, it may access $n + c$ Byte of read-write memory. The memory $d$ takes up is read-only and not accounted for. It may have a function which for any $p, k \in \mathbb{N}, B \in \{\text{C program}\}, d$ returns the $k$th Byte of $B(n, d)$'s memory after $p$ steps.

For any of the situations $B \in \{\text{Turing machine*}, \text{random-access machine*}, \text{C program}\}$: Is there an $A$ which decides whether $B(n, d)$ will halt?

I care about the reasons as to why this is the case. Unfortunately, I forgot a lot of what I learned about computability. I'm sorry if this is super trivial or unknown.

  • $\begingroup$ Can you clarify whether $n$ is a parameter of the programs or of the machines? I mean, can the programmer of $A$ and $B$ assume to know the size of the memory of the machine? $\endgroup$ – danieleds Jun 6 '17 at 7:02
  • $\begingroup$ @danieleds $n$ is a parameter of the machines. The programmer of the machines doesn't know $n$ when programming. But you can assume to be able to read $n$ at runtime. $n$ then is part of $d$. $\endgroup$ – UTF-8 Jun 6 '17 at 10:52

Yes (for Turing machines)

$A(n,B,d)$ can decide whether $B(n,d)$ will halt.

Note the fact that $B$'s writable memory is limited to $n$ units. This means that the number of possible states of $B$ is just $2^n$ (each possible memory configuration that $B$ may assume). Note also that $B$ halts iff it never goes back to a previously visited state, otherwise it would loop. This means that, if $B$ halts, it cannot do more than $2^n-1$ state transitions (as each state is visited only once).

Thus we can exploit the $2 \cdot n + c$ writable memory units of $A$ to build a machine which simulates B and counts the number of states it visits. We can do that by keeping the memory of $B$ in the first $n$ units, and a state counter $\gamma$ in some other $n+1$ units. We increment $\gamma$ at each state transition of $B$.

If $B$ halts, sooner or later the simulation of $B$ will reach a "HALT" instruction, and then we know $B$ halts. If $B$ does not halt, $\gamma$ will increase forever: as soon as $\gamma = 2^n$, we know that $B$ does not halt.

  • $\begingroup$ This only works depending on the answer to this question. $\endgroup$ – UTF-8 Jun 9 '17 at 16:57

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.