# Questions tagged [halting-problem]

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

258 questions
Filter by
Sorted by
Tagged with
98 views

### Showing $1$-reducibility of $\overline{\text{HALT}'}$ to index set

Note: overline denotes complement I am trying to show that $\overline{\text{HALT}'}\leq_1 \{i\colon\Phi_i=\Phi_e\}:= A$ for some fixed $e$ but I am misunderstanding the problem or method and can't ...
477 views

### What Turing's proof of Halting Problem really proves?

This is something that has bugged me for a while, so I hope you can help me. Suppose: $A'$ is the set of all programs, $halt?$ is the halting problem solver, $D$ is the program that is constructed ...
430 views

### Non recursively enumerable language proof by reduction to non-HP

I am trying to understand how the reduction proof for non r.e. languages works by following the examples from this website. In most cases to prove that a language is not r.e., you can reduce the ...
726 views

### Which Turing machine problems are Decidable?

Let $M_0$, $M_1$, $M_2$,..., be an effective enumeration of all Turing machines. Which of the following problems is (are) decidable ? Given a natural number $N$, does $M_N$ starting with an empty ...
192 views

### Is there any demonstrably uncomputable concrete problem which does not rely on diagonalization?

So diagonalization as we all know is an extremely productive way of showing uncomputability, the other main tool used by CS people for this task being reduction. But it has occurred to me that I do ...
59 views

### Reducing Halting Problem to Acceptor for TM

We have $A_{TM}=\{(M,w)|M$ is a TM, $w\in \Sigma^*_{TM},M$ accepts $w\}$ We intend to show that $HALT(M,w)\leq_T A_{TM}$ i.e. if we are given a machine for $A_{TM}$, we can decide whether $M$ halts ...
26 views

### How did Turing prove that there is no general process to determine whether a Turing Machine is unsatisfactory?

In the book The Annotated Turing, Charles Pezold writes: Because Turing Machines are entirely defined by a Description Number, it might be possible to create a Turing Machine that analyzes these ...
326 views

### Under which operations is the class of non-recursive languages a closure?

I am currently studying turing computability and related problems such as the halting problem with a background in formal languages. I know that the class of recursive (decidable) languages is a ...
96 views

### Can we prove that a time machine is impossible using the Halting Problem?

Let us take a hypothetical machine i which halts on the ith day of the month if it rains on the ...
17 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 ...
196 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 ...
416 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 ...
90 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$ ...
112 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 --> ...
360 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 ...
221 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)$ ...
64 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 ...
193 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 ...
82 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 ...
278 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 \...
129 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 ...
200 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 ...
86 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 ...
372 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 ...
113 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 ...
772 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 ...
401 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 ...
594 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 ...
49 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 ...
176 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 ...
110 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 ...
269 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 ...
189 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 ...
570 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

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