# Questions tagged [halting-problem]

Questions concerning the Halting problem which is to decide whether a given a program halts on a given input.

299 questions
Filter by
Sorted by
Tagged with
18 views

### Is there evidence to suggest Macsyma was directed at the Diophantine equations in the Entscheidungsproblem?

I'm reading the book The Annotated Turing by Charles Petzold. In it he mentions the Diophantine equations - which was a joy to read. This then lead to Hilbert's 10th problem - finding an algorithm ...
220 views

### Is there any way to get “around” the halting problem?

As I understand it, one proof of the Halting Theorem is done by contradiction; we assume we have program X which can determine if any program terminates. We input program X into program X (with some ...
508 views

### Explanation of an explanation of Turing's proof to the halting problem?

I am reading the transcription of a lecture from a professor Scott Aaronson, specifically the section titled Turing Machines. In this section he describes Turing's proof of the Halting Problem. But ...
95 views

### Is this padded version of the Halting Problem in NP?

I'm using the following definition of $NP$: $$A \in NP \Longleftrightarrow A(x) = \exists w: B(x,w)$$ where $B \in P$ and $|w| = poly(|x|)$. Now instead of the problem whether the program $\Pi$ ...
135 views

### How does the halting theorem interact with the recursion theorem?

Recursion theorem (paraphrasing Sipser, Introduction to the Theory of Computation): Let T be a program that computes a function t: N x N --> N. There is a program R that computes a function r: N --> ...
513 views

### Chaitin's constant is normal?

According to this source, Chaitin's constant $\Omega$ is normal. Each halting probability is a normal and transcendental real number that is not computable, which means that there is no algorithm ...
258 views

### Mapping reduction from $A_{TM}$ exercise

Let $L = \{\langle M \rangle \mid \text{M is a TM which accepts only the string "010"}\}$. Prove that $L$ is undecidable. This is my solution, reducing $A_{TM}$ to $L$: $R(\langle M,w \rangle)$ ...
69 views

### Are there algorithms for which we cannot determine if they ever halt? [duplicate]

My understanding of the halting problem in layman's terms is that there is no algorithm which will accept an arbitrary program as input and return true if it halts and false if it does not. For a ...
212 views

### How do we know that the reduction is correct?

I'm having a really difficult time understanding the logic behind reduction of the halting problems to other problems in order to prove them undecidable. Here's my reasoning: Let's say that we want ...
103 views

### Given a Turing Machine M and a string $x$ how do we tell whether a the Turing Machine M loops on the string $x$

Let us say there is a Turing Machine $M$ and a string $x$. So now I want to know if $M$ accepts or rejects the string or loops on it. So, I feed the string to $M$. So, if $M$ is accept or reject the ...
391 views

### Is a language of some deciders decidable?

Is $$L = \{ \langle M \rangle \mid M = (\{Q_1, Q_2, . . . , Q_{100}\}, \{0, 1\}, \{0, 1, \_\}, δ, Q_1, Q_2, Q_3) \text{ is a decider}\}$$ decidable? I know HALT_{TM}= \{ \langle M \rangle \...
137 views

### Turing machine for which it is impossible to decide if it halts?

Assuming someone tries to approximate a function which decides if a turing machine halts or not. It uses only a finite amount of time. The function returns $0$ (=the turing machine halts), $1$ (=the ...
248 views

### What is the meaning and significance of a Turing machine taking a description of itself as input?

Currently I'm reading about the Halting problem. $H(\langle M,w\rangle)$ is a machine which will solve the Halting problem, and then using machine $H$ one creates a new machine $D$ and we run $H$ on ...
105 views

### What is the complexity of timing a turing machine? [duplicate]

I can't find the standard name for this problem, so lets call it TIMING, it takes as input a Turing machine $F$ with its input $i$, and a number of steps $n$. It returns yes if $F(i)$ halts in less ...
501 views

### Computer Security versions of the Halting Problem

I'm plenty familiar with the Halting Problem for Turing Machines. It occurred to me after reading several posts on this site that it would be interesting, educational and useful to start a list of ...
148 views

### Why would total comparison of functions solve the Halting problem?

Why would total comparison of procedures solve the Halting problem? I've read that if all procedures could be represented syntactical e.g. in Scheme, then they could be compared structurally using ...
1k views

### Example of a language that is neither recognizable nor co-recognizable?

Is there an example of a language that is neither recognizable nor co-recognizable? A relevant (easy) theorem is that a language is decidable iff it is recognizable and co-recognizable. An example ...
511 views

### decidability of artificial intelligence

Not sure whether this is the correct place to post the question. some of my terms might not accurate. currently AI is used for classification, inference, and so forth, is AI problem decidable? for ...
721 views

### What is the amount of programs for which we can solve the halting problem?

The halting problem is undecidable of course. This implies that there is at least one program for which we cannot decide whether it halts or not, because theoretically, if all we know is that the ...
51 views

### How big is the class of problems that can be analysed to halt with static analysis. Is this class sufficient for any practical purposes? [closed]

When the halting problem is discussed, often the counterproof consists of some unsolved mathematical problem or a self-reference. Is the halting problem decidable for pure programs on an ideal ...
4k views

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

It's fairly simple to understand why the halting problem is undecidable for impure programs (i.e., ones that have I/O and/or states dependent on the machine-global state); but intuitively, it seems ...
206 views

### Are Turing machines with a limited but exponential tape decidable?

The Halting problem for Turing machines which work on a tape of at most $k$ cells can be solved: There is a limited number of distinct configurations available, providing an upper bound of steps ...
124 views

### Halting problem and simulation of intelligence [duplicate]

According to halting problem, there is no algorithm which can decide if another algorithm and its input will halt or not. Suppose human intelligence can be simulated in a computer. Also suppose than ...
277 views

### If modern computers aren't actually Turing-complete, does that mean that it is possible to determine if a program run on such a computer halts?

The halting problem says that it is impossible to create a general algorithm which can for all inputs and programs determine whether they halt. However, this assumes that the programs and/or the ...
203 views

### Misunderstanding Turing's Halting-Problem Argument

I just watched a video by Computerphile on the halting problem (https://www.youtube.com/watch?v=macM_MtS_w4) . I’m having some difficulty understanding the argument as it is made. Let me explain it ...
675 views

### Machine Learning to predict the Halting Problem

I seem to recall an academic paper from some years ago which used machine learning (possibly genetic or evolutionary programming) to predict whether a Turing Machine would halt. By predict, I mean ...
3k views

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

On this site there are many variants on the question whether TMs can decide the halting problem, whether for all other TMs or certain subsets. This question is somewhat different. It asks whether ...
2k views

68 views

### Theoretical justification of “halting problem avoidance”

The wikipedia page for the Halting problem mentioned practical solutions to avoiding the halting problem such as avoiding infinite loops. And there is a mention that "by restricting the capabilities ...
1k views

2k views

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

This question occurred to me about the halting problem and I couldn't find a good answer online, wondering if someone can help. Is it possible that the halting problem is decidable for any TM on any ...
964 views

### Undecidability of telling if a program returns true or false

Consider the problem of taking an input Turing machine and determining if the final cell is a $0$ or $1$ after computation halts. On cases where it writes something else or does not halt, you are ...
5k views

### What does it mean to be Turing reducible?

I'm confused about what it means to be Turing reducible. I thought I understood what it meant, but apparently not. $A \leq B$ Means that A is Turing reducible to B. This means that given an oracle ...
2k views

### Show that the Halting problem is reducible to its complement

HALT$_{TM}$ is the set of all machine-input pairs $<M,w>$ where $M$ halts on input $w$ The complement of HALT$_{TM}$ is the set of all machine-input pairs $<M,w>$ where $M$ ...
23 views

### IsDefined predicate computable?

I am working on a computability assignment, I want to define a helper predicate IsDefined by: $IsDefinied(x,n) = \{ 1$ if $\Phi^{(1)}(x,n)$ is defined, $0$ otherwise. Where $\Phi^{(1)}$ is the ...
5k views

### Proof by Reduction: From Empty Language to Halting Problem on Empty Input

Question: Let language $E$ = {$\langle M \rangle$ | $M$ accepts no inputs whatsoever} Let language $H$ = { $\langle M \rangle$ | $M$ halts on an empty string input}. Is it possible to show that $H$ ...