Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

# Tag Info

42

The halting theorem, Cantor's theorem (the non-isomorphism of a set and its powerset), and Goedel's incompleteness theorem are all instances of the Lawvere fixed point theorem, which says that for any cartesian closed category, if there is an epimorphic map $e : A \to (A \Rightarrow B)$ then every $f : B \to B$ has a fixed point. Lawvere, F. William. ...

37

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

32

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

22

An extended comment: Collatz-like sequences can be computed by small Turing machines having few symbols and states. In "Small Turing machines and generalized busy beaver competition" by P. Michel (2004), there is a nice table that positions Collatz-like problems between decidable TMs (for which the halting problem is decidable) and Universal TMs. There ...

15

A single Turing machine can simulate a network of Turing machines and all communication between them (if you prefer to think about real computers, you could simulate/virtualize several computers on one computer). So whatever a network of TMs can compute, a single TM can compute, too.

14

It's not a hidden link but one that has been made explicit using the language of category theory and also a very natural question to ask and study. There is a fair bit of material on the subject. CS Theory question asking the same thing Andrej Bauer's blog post about fixed point theorems and Cantor's theorem. A Universal Approach to Self-Referential ...

11

Because one of the principal applications of Type Theory in formalizations has been to study programing languages and computation in general, a lot of thought has gone into ways of representing possibly non-terminating programs. I won't make a complete survey here, but I'll try and give pointers to the main thrusts of different directions. The "relational" ...

11

I'm glad you are interested in complexity but there are some issues in your paper. Your techniques relativize and there is an oracle relative to which the Berman-Hartmanis conjecture is true and NP = EXP. The main issue is that you can't do self-reference for time-bounded machines since you can't simulate and stay within the time bound.

10

This isn't a "nice" property, because whether it's true or false depends upon the encoding. See David et al's Asymptotically almost all $\lambda$-terms are strongly normalizing, which proves what it says in the title. However, this paper also shows that the opposite holds for SKI-combinators (into which lambda-terms can be compositionally embedded). In ...

9

Termination of a Turing machine (on a fixed input) is a $\Sigma^0_1$ sentence and all usual first-order arithmetic theories are complete for $\Sigma^0_1$ sentences, i.e. all true $\Sigma^0_1$ statements are provable in these theories. If you look at totality in place of halting, i.e. a TM halts on all inputs, then that is a $\Pi^0_2$-complete sentence and ...

9

I believe that some version of this connection can be tied back to Turing's seminal paper on computability. Namely, Turing makes the following two claims: "The results of Section 8 have some important applications. In particular, they can be used to show that the Hilbert Entscheidungsproblem can have no solution." "If the negation of what Godel has ...

7

It depends in which sense you mean "undecidable". If you evaluate $M$ on the empty input, and want only to find a yes/no answer, then the algorithmic problem is trivially decidable, as answered by Gamow, since either the algorithm outputting "Yes", or the one outputting "No" is correct. you don't have to know which one is correct to prove decidability: ...

6

Gödel's incompleteness theorem can be thought of as a reduction from the Halting problem to the language $\langle \varphi \mid \varphi \text{ is a true sentence in number theory}\rangle$, and a careful analysis of the running time would show that it is indeed a polynomial time reduction. Not every such reduction is polynomial time, however. You can observe ...

6

As a counter-example to this, consider the Context-Free Equivalence problem: it's undecidable to determine, given two context free languages, whether they accept the same set. If your problem were decidable, we could use it to determine CFL equivalence, since it's always possible to turn a CFL into an always-halting Turing machine. So even for countably ...

5

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. 5 I also think that a very similar question has been asked before, I think first here: https://mathoverflow.net/questions/27967/decidability-of-chess-on-an-infinite-board/63684 Here is my updated and modified opinion. I think the problem is not solved completely, but the answer is almost surely yes. I do not have a proof for chess, as I lack the ability to ... 5 The mortality problem is undecidable (P.K. Hooper, Th eUndecidability of the Turing Machine Immortality Problem (1966)) The uniform mortality problem undecidability follows from the following: Theorem: A Turing machine is mortal if and only if it is uniformly mortal I found the proof in: Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson, Moshe Y. ... 4 Consider programs$e_1$,$e_2$and numbers of time steps$t$. Let$f_i(t)$be the output of$e_i$after$t$steps, and let$f_i(t)$output a special message like "none" if there's no output yet. Then$f_1$and$f_2$both always halt, but you can't decide if they always output the same - see Rice's Theorem. 4 Yes, an example of a system that performs this task is T2. It does not solve the halting problem but instead it only attempts to solve certain special cases. A overview is at https://en.wikipedia.org/wiki/Microsoft_Terminator . The newest version of this system is at https://mmjb.github.io/T2/ . 4 Yesterday I googled around to check the status of this problem and I found this new (2012) result: Dan Brumleve, Joel David Hamkins and Philipp Schlicht, The mate-in-n problem of infinite chess is decidable (2012) So the mate-in-n problem of infinite chess cannot be Turing complete. The decidability of infinite chess with no restrictions on the number ... 4 The question was answered by Emil Jerabek at https://mathoverflow.net/questions/115275/non-uniform-complexity-of-the-halting-problem 4 Just an extended comment: I'm not an expert, but for what regards 1., something can be said if you interpret:$HALT(k) = 1$iif$TM_k$halts on the empty tape. In this case the string$s$that lists the first$n$bits$HALT(k)$,$k = 1,2,...,n$is highly compressible:$|s|=n$let$h$be the number of halting TMs between$1$and$n$($h \leq n$) If you ... 4 This is another way to prove that not all Turing machines are predictable. First it's easy to note that: all halting machines are predictable; all machines that loop forever on a finite portion of the tape are predictable; all machines that expand towards both sides of the tape are predictable ($N=M, Q' = \emptyset$). The interesting case is when a ... 3 Consider the function$T: \mathbb N \rightarrow \mathbb N$, where$T(n)=n/2$when$n$is even and$T(n)=n+1$when$n$is odd. Then it is known that for any$n \in \mathbb N$, there exists a$k \in \mathbb N$such that$T^{(k)}(n)=1$. If instead of$T(n)=n+1$when$n$is odd, we had defined$T(n)=3n+1$when$n$is odd, we would have the Collatz Conjecture, ... 3 Let's call your answers "yes" (the given program halts), "no" (the given program does not halt) and "maybe". If I understand you correctly, you are redefining the Haltin problem as follows. Zirui's Problem: Is there a machine$M$such that, on a given input$k$representing a machine$K$,$M$halts and: if$K$tries to trick$M$then: if$K$... 3 The usual proof that the halting problem is undecidable already gives you exactly such an algorithm. Given an algorithm$A$, we construct an algorithm$B$that on input$x$computes$A$on program$x$and input$x$, and then enters an infinite loop iff$A$answered "halts". Now consider giving$B$itself as an input. If$A(B,B)=\text{"halts"}$then$B$doesn'... 3 I'm not a logic expert, but I believe the answer is no. If the Turing machine halts, and the system is strong enough, you ought to be able to write out the full computation history of the Turing machine on its input. When one verifies that the result of the computation is a terminating sequence of transitions, one can see that the machine halts. ... 2 No, there is a whole hierarchy of Turing undecidability: http://en.wikipedia.org/wiki/Turing_degree In particular, the language L_max consisting of all minimal Turing machine encodings is not reducible to L_halt. (A TM encoding is minimal if there is no shorter encoding of an equivalent TM). 2 A finite prefix of$G$is$G \cap \{0,1,\ldots n\}$for some$n$. It is easier if you look at the characteristic function of$G$which can we viewed as an infinite word in$2^\omega$. Then a finite prefix is a finite initial part of$G\$. For forcing, there are many resources, depends on what you want to learn. A point to start is the Wikipedia pages and ...

2

This is answering the title of the question more than its content, but you can also consider "approximations" of the halting problem as algorithms which will give you a correct answer on "almost all" programs. The notion of "almost all" programs only makes sense if your model of computation is optimal (in the same sense that for Kolmogorov's complexity), to ...

Only top voted, non community-wiki answers of a minimum length are eligible