I know that the halting problem is undecidable in general but there are some Turing machines that obviously halt and some that obviously don't. Out of all possible turing machines what is the smallest one where nobody has a proof whether it halts or not?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
The largest Turing machines for which the halting problem is decidable are:
$TM(2,3), TM(2,2), TM(3,2)$ (where $TM(k,l)$ is the set of Turing machines with $k$ states and $l$ symbols).
The decidability of $TM(2,4)$ and $TM(3,3)$ is on the boundary and it is difficult to settle because it depends on the Collatz conjecture which is an open problem.
See also my answer on cstheory about Collatz-like Turing machines and "Small Turing machines and generalized busy beaver competition" by P. Michel (2004) (in which it is conjectured that $TM(4,2)$ is also decidable).
Kaveh's comment and Mohammad's answer are correct, so for a formal definition of the standard/non-standard Turing machines used in this kind of results see Turlough Neary and Damien Woods works on small universal Turing machines, e.g. The complexity of small universal Turing machines: a survey (Rule 110 TMs are weakly universal).
I would like to add that there are some Turing Machines for which the Halting problem is independent of ZFC.
For instance take a Turing machine which looks for a proof of contradiction in ZFC. Then if ZFC is consistent, it won't halt, but you cannot prove it in ZFC (because of Gödel's second incompleteness theorem).
So it is not only a matter of not having found a proof yet, sometimes proofs don't even exist.
No one has a proof whether Universal Turing machine halts or not. In fact, such proof is impossible as a result of the undecidability of the the Halting problem . The smallest is a 2-state 3-symbol universal Turing machine which was found by Alex Smith for which he won a prize of $25,000.
an inexactly phrased but reasonable general question that can be studied in several particular technical ways. there are many "small" machines measured by states/symbols where halting is unknown but no "smallest" machine is possible unless one comes up with some justifiable/quantifiable metric of the complexity of a TM that takes into account both states and symbols (apparently nobody has proposed one so far).
actually research into this problem related to Busy Beavers suggests that there are are many such "small" machines lying on a hyperbolic curve where $x \times y$, $x$ states and $y$ symbols, is small. in fact it appears to be a general phase transition/boundary between decidable and undecidable problems.
this new paper Problems in number theory from busy beaver competition 2013 by Michel a leading authority exhibits many such cases for low $x,y$ and shows the connection to general number theoretic sequences similar to the Collatz conjecture.