# Tag Info

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$ ...
• 4,322
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 ...
• 6,170
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), ...
• 727
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. ...
• 8,303

### 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$ ...
• 81.9k
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 ...
• 81.9k
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 ...
• 81.9k
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 ...
• 161k
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 ...
• 278k
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 ...
• 371
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 ...
• 3,800

### 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 ...
• 278k
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 ...
• 30.9k
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 ...
• 2,521
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: ...
• 3,183

### 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.
• 1,058

### 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 ...
• 9,465
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 ...
• 72.6k
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 ...
• 7,088

### 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$ ...
• 81.9k

### 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 ...
• 81.9k

### 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 ...
• 161k

### 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.
• 161k
Accepted

• 278k