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.

  • $\begingroup$ To proof undecidability you should use a property that separates R and RE languages (i.e. decidable and recognizable languages). $\endgroup$ – Parham Dec 13 '13 at 20:14
  • $\begingroup$ This language is not decidable, but it is recursively enumerable (also known as semidecidable). $\endgroup$ – D.W. Dec 14 '13 at 5:14
  • 1
    $\begingroup$ You need to clarify, is there a limit to how many cells can be written during the computation? i.e. is the entire tape only 100 cells long, or does it always start with input of size 100 or less, but can write past cell 100? $\endgroup$ – jmite Dec 14 '13 at 19:18
  • $\begingroup$ This is the question as I found it on the exam-paper (I'm looking at exams for earlier years in my course (Norwegian course, so this is translated), and the solution given to that exam is by the professor). I'm not completely sure, but I think it is meant that the input length is constrained to a length of 100, and that it is no constraints on the tape size. (Thanks for all your replies by the way, I'm learning a lot on reflecting on what you write). $\endgroup$ – Michael Dec 15 '13 at 13:46
  • $\begingroup$ I've sent an e-mail to the professor in my course, to ask for a clarifying (I gave him a link to this page, so hopefully he answer here). $\endgroup$ – Michael Dec 15 '13 at 14:10

@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.

  • 1
    $\begingroup$ This only holds under the assumption that there is a limit of 100 cells that can be written on the tape, which the question does not specify. The question mentions an input of size 100, not that there are only 100 tape cells that can be written to during the compmutation. $\endgroup$ – jmite Dec 14 '13 at 19:17
  • 1
    $\begingroup$ I would make an educated guess that this is what was meant, but of course technically you are correct. Even with 0 input cells, if the machine may use unbounded amounts of tape, then the language is just the halting set, so obviously not decidable. It is better to interpret an exercise in a reasonable way, and point out later that the phrasing is wrong. If you interpret it so that it becomes trivial, nobody will learn anything from it. So, thanks for the comment, I will edit my answer to point out that this is hapenning. $\endgroup$ – Andrej Bauer Dec 14 '13 at 20:50

Yeah, their answer is wrong. If it were right, you could solve the halting problem. You can tell this since (a) all strings have some finite length and (b) the number 100 was pulled out of thin air, and their argument works the same way for any finite number. If you could just simulate a TM on an input to tell if it halts on the input, the halting problem would be decidable, since all TMs can be simulated.

  • $\begingroup$ Your reasoning is faulty. While it is true that 100 can be replaced with any number, this does not help because you cannot tell in advance which number you should use. It is crucial for decidability of the language $L$ that the number is given in advance and not changed as the machine is simulated. $\endgroup$ – Andrej Bauer Dec 14 '13 at 7:52
  • $\begingroup$ @AndrejBauer How is my reasoning faulty? You imagined some other question into the OP, and it just so happened that this was the question Michael meant to ask. My answer and reasoning are correct for the question, as is. That said, since your answer was accepted, you should really consider editing the question, so that other people with the same question can benefit from your answer. As it is, people might come here, read the question, and leave, thinking this isn't their question. $\endgroup$ – Patrick87 Dec 16 '13 at 15:40

I believe the given solution is wrong.

The problem is, for an arbitrary machine $M$, it is undecidable if any word $w\in L(M)$. This comes easily from Rice's theorem.

So their technique of "try all words of length less than 100" doesn't work, because there is no guarantee that you will halt when trying those words.

Perhaps they're confusing R and RE? The problem is, in fact, recursively enumerable: since you only need to try a finite number of inputs, you will always halt if the test machine halts for every input of length less than 100. But there is no guarantee that you will halt if it doesn't halt for some input of length less than 100.

  • $\begingroup$ You missed the fact that when a machine is simulated on a tape with 100 cells, we need not simulate it forever. We can calculate an upper bound on how much simulation is needed, because the machine will either halt or repeat a configuration within that many steps, see my answer. $\endgroup$ – Andrej Bauer Dec 14 '13 at 7:53
  • $\begingroup$ Okay... there is a huge difference between input of size 100 and tape size of 100. $\endgroup$ – jmite Dec 14 '13 at 19:14
  • $\begingroup$ Not sure why Andrej's so convinced the question must be about tape length. The word "input" is used over and over again in the question. Perhaps it's a translation issue from the Norwegian? Are the terms for "input" and "input tape" the same? $\endgroup$ – Patrick87 Dec 16 '13 at 15:45
  • $\begingroup$ The correct thing to do in face of an unclear question is to downvote the question until it gets clarified. $\endgroup$ – Andrej Bauer Dec 16 '13 at 16:18
  • 1
    $\begingroup$ @AndrejBauer Well, that's the thing: until you came, the question was perfectly clear... just a different question than what it appears to be becoming. $\endgroup$ – Patrick87 Dec 16 '13 at 16:23

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