Skip to main content
14 votes

What is the smallest Turing machine where it is unknown if it halts or not?

Overview of Turing Machine decidability starting on the a blank tape (Busy Beaver style) For the blank tape input only (as opposed to the more traditional Busy Beaver statement which asks decidability ...
Ciro Santilli OurBigBook.com's user avatar
13 votes
Accepted

Is there a good notion of non-termination and halting proofs in type theory?

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 ...
cody's user avatar
  • 13.9k
11 votes

"Berman-Hartmanis Conjecture Separates NP From All Super-Poly. DTIME Classes" -- Worthy of arXiv.org?

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 = ...
Lance Fortnow's user avatar
10 votes
Accepted

How good can a halting detector be?

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 ...
Neel Krishnaswami's user avatar
9 votes
Accepted

For a specific unbounded Turing machine, is its Halting problem undecidable?

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 ...
Denis's user avatar
  • 8,903
9 votes
Accepted

What is the reference for the proof Gödel's first incompleteness theorem based on the undecidability of the halting problem?

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 ...
Yonatan N's user avatar
  • 1,642
8 votes
Accepted

Can the halting problem be solved probabilistically?

It is well known that any language or function computable by a probabilistic algorithm is also computable deterministically. Here, we require that with probability $>1/2$, the algorithm outputs the ...
Emil Jeřábek's user avatar
6 votes
Accepted

Uniform mortality problem for Turing Machines

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: ...
Marzio De Biasi's user avatar
6 votes

For a specific unbounded Turing machine, is its Halting problem undecidable?

For every concrete Turing machine $M$, the halting problem (Problem $P_M$ without input: "Does the Turing machine $M$ halt on the empty input $\varepsilon$?") is decidable. The corresponding decision ...
Gamow's user avatar
  • 5,772
6 votes

Is there a sensible notion of an approximation algorithm for an undecidable problem?

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" ...
Ted's user avatar
  • 329
6 votes
Accepted

Program equivalence wherein the programs are known to always halt

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 ...
Joey Eremondi's user avatar
4 votes

Program equivalence wherein the programs are known to always halt

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. ...
Bjørn Kjos-Hanssen's user avatar
4 votes
Accepted

Practical approaches to solving whether programs will halt

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/...
Joshua Herman's user avatar
4 votes
Accepted

Turing meta-oracle

Such an $H$ would let us solve the halting problem: We begin by running $H(H(P))$ until it halts (which it does by assumption on $H$). If the output of $H(H(P))$ is "doesn't halt," then we know $H(P)...
Noah Schweber's user avatar
4 votes
Accepted

Are all turing machines paths predictable?

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 ...
Marzio De Biasi's user avatar
3 votes
Accepted

Is this a weaker or stronger form of the halting problem

The standard proof that the halting problem $L$ is undecidable also gives an efficient algorithm for constructing an instance on which a given Turing machine $H$ fails to solve the halting problem. ...
William Hoza's user avatar
  • 1,743
2 votes

Halting problem proofs that do not utilise self-reference or diagonalization

P1 Perhaps you can somewhat avoid self reference in this way. Let $S_k$ be the total number of steps performed by the halting Turing machines of size $\leq k$ in their computation. Suppose the Halting ...
Marzio De Biasi's user avatar
2 votes

Is this a good definition of computability?

First of all, the place for this question is cs.se, not here. But since I've already written an answer, I'll leave it. There is a formal definition of computability: a function $f$ is computable if ...
Shaull's user avatar
  • 5,656
2 votes

Are all turing machines paths predictable?

If I understood your question correctly, the answer is NO. Let $M$ be any TM and $w$ any input string, and define the TM $M'$ as follows: it reserves the leftmost square of the tape as "special" (e.g.,...
Aryeh's user avatar
  • 10.6k
2 votes

Halting problem for finite tape TM

"Easy to check" is the understatement of the century: can you actually carry out your proposed plan of "just" writing down all the registers/RAM cells, etc? You're right that it takes finite time, but ...
Aryeh's user avatar
  • 10.6k
2 votes

Automated proving that a program doesn't halt

In contradiction with Gurkenglas' answer, there actually is a community of scientists who work on proving non-termination of programs in various language and formalisms. An obvious approach would be ...
cody's user avatar
  • 13.9k
1 vote

Automated proving that a program doesn't halt

Since the Halting problem is undecidable, whatever approach I use to answer the question must eventually be unhelpful in the real world. There's a sequence of sets of programs such that each set is ...
Gurkenglas's user avatar

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