Decidability of Turing Machines with input of fixed length

ignougroup
Problem Detail: I’m learning about undecidability, and found this question: 

Is this language decidable, make a proof:     L = { M : machine M halts for every input of length not exceeding 100 }

Update: This is translated from an exam paper some years ago, and I’m quite sure it means that machine M should halt for every input with length from 0 to 100, and that it is no constraints on the tape size. Update2: The solution given below, and hence the origin of this post, is for an variant of this question with fixed number of steps and input. Sorry for the confusion. I came to the conclusion that this is an undecidable language. My logic is as follows: Lets say for the sake of contradiction that it is possible to construct a machine $M_R$, that takes as input an arbitrary input $(M,x)$, and reduces this to $M’$. $M’$ has the property so that $(M,x) in M_{HALT}$ iff $M’ in L$, this means that $M$ halts on all $x$ of input with maximum length of 100. Then run $M$ on $x$, if it halts then accept. And shows that $M_R$ decides the halting problem, and in hence a contradiction and proves that his is not decidable. But in the solution it is written that this question is decidable:

You can simulate $M$ on all inputs of length 100 or less (you can generate such input in a loop and use the universal Turing machine to simulate M on x), it is only $|Sigma|^{100}$ possible inputs of length 100, that is finite.

Asked By : Michael

Answered By : Andrej Bauer

@jmite correctly points out that the statement is written in such a way that the language is obviously undecidable. Even with 0 cells of input, as long as the machine is able to use an unbounded amount of work tape, the language will be undecidable. This is a completely basic fact about the Halting set. @Michael should check to see whether the problem states that the machine only has 100 cells of input, or of total tape to work with. Did you transcribe the problem correctly? Given the suggested official answer (which is not very good, may I know where this problem came from?), I think the problem meant to say that the total amount of tape available is 100 cells. In which case, the answer is as follows. The language is decidable. Let us suppose the tape alphabet consists of three symbols, $0$, $1$ and blank. Given a Turing machine $M$ with $n$ states, there are at most $$n times 3^{100} times 100$$ configurations of the machine, the head and the tape: the machine can be in any one of $n$ states, each of the 100 cell tapes may contain one of three symbols, and the head may be in 100 different positions. To determine whether $M$ halts, we simulate step by step for at most $n times 3^{100} times 100 + 1$ steps. If the simulation halts, then $M$ halts, otherwise $M$ will have repeated the same configuration twice and therefore loop forever. We may even detect the repeated configuration if we wish. Let me address the other two answers:

  1. @jmite: you missed the fact that we may halt the simulation after a finite number of steps because there are only finitely many possible configurations of the machine, the tape and the state.
  2. @Patrick87: it is true that the number 100 can be replaced with any other number. So, for any machine $M$ and any number $n$ we can decided whether $M$ will halt on a tape of length $n$. This however does not allow us to deduce anything about $M$ halting on an infinite tape because $M$ could run forever by using up unbounded amounts of tape. There will be no $n$ such that $M$ uses only $n$ cells, so knowing what it does on $n$ cells won’t be helpful.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/18959