Skip to main content
38 votes
Accepted

Is the halting problem decidable for pure programs on an ideal computer?

Here is a proof of undecidability by reduction from the Halting problem. Reduction: Given a machine $M$ and an input $x$, build a new Turing Machine $H$ which does not read any input, but writes $M$ ...
Lieuwe Vinkhuijzen's user avatar
33 votes
Accepted

Can we ever achieve Turing completeness?

As far as I know we say something is turing complete (eg: a programming language) when it can compute any function and can do any task. No. A model of computation is Turing-complete if it can compute ...
Jörg W Mittag's user avatar
31 votes
Accepted

Is it provably true/false that for a program, there exists a proof whether it halts or not?

Actually this is no different from the halting problem unsolvability. If you have any formal system T with a proof verifier program V that can reason about programs (as you desire in your question), ...
user21820's user avatar
  • 727
28 votes
Accepted

Turing machine + time dilation = solve the halting problem?

Note that Turing's proof is one of mathematics, not of physics. Within the model of a Turing machine Turing defined, undecidability of the halting problem has been proven and is a mathematical fact. ...
Discrete lizard's user avatar
  • 8,303
22 votes

Is halting problem computable for particular inputs/assumptions

is halting problem computable by program P for all other programs used as input but P itself? No. Consider the infinite sequence of programs $P_1, P_2, \dots$, where $P_i$ is "Move the head $i$ ...
David Richerby's user avatar
22 votes
Accepted

Does it make sense to talk about the complexity of non-computable functions (such as the Halting problem)?

Computational complexity studies the computational resources required to decide problems in some particular model of computation. Because of this, it makes no sense to talk about the complexity of a ...
David Richerby's user avatar
21 votes
Accepted

The 'directionality' of reductions?

Don't worry – everybody gets confused by the direction of reductions. Even people who've been working in algorithms and complexity for decades occasionally have a, "Wait, were we supposed ...
David Richerby's user avatar
21 votes
Accepted

Halting Problem without self-reference: why does this argument not suffice (or does it)?

I don't think this is a good way to present the halting problem, because it sweeps a critical issue under the covers in a sneaky way. I suggest sticking with a more standard presentation, such as the ...
D.W.'s user avatar
  • 161k
21 votes
Accepted

Can a program exist that halts only if it can prove that it doesn't halt?

We can define a sound proof system as a computable function $\Pi$ which maps strings (proofs) to strings (statements proved), with the following property: if $\Pi(\pi) = p$, then $p$ encodes a true ...
Yuval Filmus's user avatar
20 votes
Accepted

Is possible to prove undecidability of the halting problem in Coq?

You're exactly right that the halting problem is an example of the second kind of "proof by contradiction" - it's really just a negative statement. Suppose ...
Tej Chajed's user avatar
20 votes
Accepted

Halting problem theory vs. practice

Languages that are guaranteed to halt have seen wide spread use. Languages like Coq/Agda/Idris are all in this category. Many many type systems are in fact ensured to halt such as System F or any of ...
Jake's user avatar
  • 3,800
19 votes

Can a Turing Machine (TM) decide whether the halting problem applies to all TMs?

The language of Turing machines deciding the halting problem is decidable. A Turing machine that decides it simply always outputs NO. In other words, $\emptyset$ is decidable. You might be confused ...
Yuval Filmus's user avatar
19 votes
Accepted

The Halting problem proof is wrong?

You are committing a logical error. This question has nothing whatsoever to do with computability and machines. It is entirely about how to prove that something does not exist. Namely, to show the ...
Andrej Bauer's user avatar
  • 30.9k
18 votes
Accepted

How to prove the existence of a number which cannot be written by any algorithm?

As Sebastian indicates, there are only (infintely but) countably many programs. List them to create a list of programs. The list is (infinitely but) countably long. Each program generates one number ...
Albert Hendriks's user avatar
18 votes
Accepted

Detecting if three Turing Machines halt given a magic oracle that is only used twice

One way to built $T_A$ works is roughly as follows: ...
Arno's user avatar
  • 3,183
17 votes

How to prove the existence of a number which cannot be written by any algorithm?

It's actually much simpler. There's only a countable number of algorithms. Yet there are uncountably many real numbers. So if you try to pair them up, some real numbers will be left hanging.
Sebastian Oberhoff's user avatar
16 votes

Is the halting problem decidable for pure programs on an ideal computer?

No it is not, and moreover it does not depend on I/O. Simple counterexample: write a program to find a perfect odd number (this is an open problem: we do not know yet whether one exists) - it does ...
Evil's user avatar
  • 9,465
16 votes
Accepted

Why is the halting problem semi-decidable?

Tl;dr: "(say) whether or not it halts" and "(say) if it halts" are not the same thing. Use mathematics to avoid confusion induced by language ambiguity. Halting problem says that for a given input ...
Raphael's user avatar
  • 72.6k
16 votes
Accepted

What is the complexity of theorem proving?

In general, the complexity of theorem proving in a particular logical system (such as ZFC) is recursively enumerable (RE), and is complete for this class -- that is, equally as hard as solving the ...
Caleb Stanford's user avatar
14 votes

Is it possible that the halting problem is solvable for all input except the machine's code?

Recall the standard proof of the undecidability of the halting problem. Suppose that some machine $H$ decides the halting problem and let $Q$ be the machine that, on input $\langle M\rangle$ ...
David Richerby's user avatar
14 votes

Is the halting problem theorem really proven

Any proof of the undecidability of the halting problem is specific to some model of computation. The proof is usually stated using Turing machines, which don't have call stacks or any other bells or ...
David Richerby's user avatar
14 votes

What does it mean to prove the halting problem is undecidable "using arithmetization"?

I would guess/assume that by "arithmetization", they mean the concept that every Turing machine can be associated with a bit-string or natural number (the fact that we can encode a ...
D.W.'s user avatar
  • 161k
12 votes

Does it make sense to talk about the complexity of non-computable functions (such as the Halting problem)?

The halting problem is not in NP. It is, however, NP-hard, which is not the same thing.
D.W.'s user avatar
  • 161k
11 votes
Accepted

Is halting problem computable for particular inputs/assumptions

If $f$ is any computable function, then $g$, defined as $$ g(n) = \begin{cases} f(n) & \mbox{if } n \neq k \\ v & \mbox{otherwise} \end{cases} $$ is also computable, for any choice of $...
chi's user avatar
  • 14.6k
10 votes
Accepted

Chaitin's constant is normal?

In contrast to your example, Chaitin's constant is not defined as follows: $$ \Omega = \sum_{n\colon \text{$n$th program halts}} 2^{-n}. $$ Instead, there is a set $\Pi \subseteq \{0,1\}^*$ of ...
Yuval Filmus's user avatar
10 votes

Turing machine + time dilation = solve the halting problem?

The Turing machine is a formal mathematical model of computation, it does not answer to any physical limitations and does not care about relativistic effects. This means that Turing's proof does not ...
Ariel's user avatar
  • 13.4k
9 votes
Accepted

Halting problem with Proof of The Immerman-Szelepcenyi Theorem (knowledge of the theorem might not be necessary to clear my doubt)

As the proof (sketch) itself notes: Note that on a given input $x$ of length $n$ there are $2^{f(n)}$ possible configurations. This means there is only a finite space of configurations for a ...
cody's user avatar
  • 8,233
9 votes

How to prove the existence of a number which cannot be written by any algorithm?

Consider the number whose $k$th digit is $1$ if the $k$th Turing machine halts on the empty input, and $0$ if it doesn't halt. If you could generate the digits of this real number then you could solve ...
Yuval Filmus's user avatar
9 votes

The Halting problem proof is wrong?

First, let us see what the halting proof attempts to prove: There is no program $H$ that, on input $(x,y)$, always halts, and returns whether the program encoded by $x$ halts when run on the input $...
Yuval Filmus's user avatar
9 votes

Can a program exist that halts only if it can prove that it doesn't halt?

Your program P may halt if the proof system it is using is inconsistent, allowing it to prove a self-contradictory statement. The fact that no (sufficiently expressive) proof system can prove its own ...
Ilmari Karonen's user avatar

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