# 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
56 views

### Under what kind of oracles are $P$ and $NP$ equivalent?

How strong have the oracles needed to be for these two classes to be proven equivalent with respect to them? For instance: is $P^H$ = $NP^H$ (ie. is $P$ equipped with an oracle to solve the halting ...
36 views

### If a turing machine can't solve the halting problem for a machine X, does this imply that X is at least as powerful as a turing machine?

Say I have a deterministic machine X, and I prove that a turing machine can't solve the halting problem for this machine when given a certain input. Does this imply that this machine X is turing-...
32 views

### proving $E_{TM}$ is undecidable using the halting language

How to prove that: $E_{TM} = \{\langle M\rangle\mid M \ is\ a\ TM\ and\ L(M)=\emptyset\}\notin R$ (is undecidable) using the language: $H_{halt}=\{(⟨M⟩,w):M\ halts\ on\ w\}$. I tried to prove by ...
30 views

### Is the undecidability of a given problem undecidable?

Given an input problem P, can you construct an algorithm A to compute whether or not P is decidable or undecidable? In other words, is the undecidabiliy of a problem undecidable? My initial guess is ...
26 views

39 views

### Constructing a Turing machine which decides whether a fixed TM will halt on a fixed input or not

It is known that the halting problem is decidable for every fixed $M_0$ Turing machine and every fixed $w_0$ input. My related question would be the following: is it true that for every fixed $M_0$ ...
111 views

### Halting problem for fixed Turing machine and fixed input

It is known that the halting problem is undecidable even when we fix either the Turing machine $M$ or the input $w$. What if we fixed both the machine and the input? I.e., is it decidable for every ...
26 views

### Proving undecidability of HALT_tm by reduction

Sipser in his book introduction to the theory of computation provided a proof of undecidability of $HALT_{TM}$. He uses a contradiction, he assumed that $HALT_{TM}$ ...
48 views

### Help with finding a flaw in argument simulating large Turing machines with smaller ones

I have an argument which, if it goes through, just about proves that either: Programming languages are more powerful than Turing machines The busy beaver function ($BB()$) on Turing machines is ...
76 views

### Can we find a Turing machine such that there is no Turing machine to decide whether it halts on $\epsilon$?

The halting problem states that there is no Turing machine that can determine whether an arbitrary Turing machine halts on $\epsilon$. But I try to ask something different, can we find a specific ...
44 views

### Are non halting programs not computable?

Are non halting programs not computable? How are these two sets of programs related: is a non halting program just a specific example of a type of program that is not computable or is it technically ...
44 views

### Union of halting-like problem and non-halting-like problem

I came across the following problem: Define languages $L_0$ and $L_1$ as follows : $L_0=\{⟨M,w,0⟩∣M\text{ halts on }w\}$ $L_1=\{⟨M,w,1⟩∣M\text{ does not halt on }w\}$ Here $⟨M,w,i⟩$ is ...
27 views

### how is the set of undecidable programs related to the set of non-halting programs?

Is there a non-halting program for every undecidable program? is undecidable the "same thing" as non-halting? Thanks!
196 views

### Undecidability of two Turing machines acting the same way on an input

So I need to find a reduction to the (undecidable) problem of deciding if two Turing machines $M_1$ and $M_2$ behave the same way on an input $x$. "Behaving the same way" is defined like this: $M_1$ ...
51 views

### In the reduction from HALT to ALLHALT, why does the constructed Turing machine loop indefinitely when the inputted Turing machine rejects?

Let HALT be the language $\{\langle M, w\rangle : M\text{ is a TM that halts on }w \}$. Let ALLHALT be the language $\{\langle M\rangle : M\text{ is a TM that halts on all inputs}\}$. Use a reduction ...
21 views

### Proving Problems are Undecidable/ Semi decidable? E.g. Halting Problem, Membership Problem? [duplicate]

I am having issues finding similarities in different cases where a problem such as the Halting Problem or the Accept-Λ problem is reduced to the Membership problem to prove that it is semi-decidable ...
54 views

### TM1 accepts w1 vs TM1 halts on w1

What is difference between following two problems, their decidability and recognizability status: Given Turing Machine TM "accepts" given string w. Given Turing Machine TM "halts on" given string w. ...
33 views

### is the empty language L = ∅ a subset of every languages?

I need to show false the following claim Every language L which is a subset of $A_{TM}$ ($L \subseteq A_{TM}$) is undecidable. For this, I wish to use the empty language L = ∅ (I know is decidable)...
80 views

### if A is decidable then B is decidable too

Assume that a language A is reducible to language B. The claim is true? if A is decidable then B is decidable too. The correct answer is: This claim is wrong. If A is e.g. the empty language (...
17 views

### Is checking if the length of a C program that can generate a string is less than a given number decidable?

I was given this question: Komplexity(S) is the length of the smallest C program that generates the string S as an output. Is the question "Komplexity(S) < K" decidable? With respect to ...
141 views

### Are there any problems that reduce to the halting problem?

I'm reading through sipser and there is a lot of computability problems that the halting problem reduces to, i.e. if $A_{TM} = \{\langle M,w\rangle : M$ accepts input $w\}$ then $A_{TM} \leq P$ where ...
128 views

### Turing recognizable but not Turing decidable language cannot have TM do not halt on infinitely many inputs

Sorry, I think I misunderstand the question, It should read as if $L$ is turing-recognizable but not decidable, then there exists infinitely many input that any TM will not halt on it...
62 views

### How can Turing complete machines exist theoretically if the halting problem is undecidable

As the question says, if I input on the tape of a Turing complete machine a program that solves the halting problem with the correct inputs the program will never end its execution regardless of ...
36 views

### On the computable function of a problem that halts

Let's say program $P$ with given input $i$ is found to halt (or doesn’t halt) by a Turing machine. Is it true that the same program $P$ with input $F(i)$ also halts (or not, respectively), where $F$ ...
54 views

### Why do intuitionists accept the nonconstructive proof that the halting problem is undecidable? [duplicate]

On the intuitionism page at Stanford Encyclopedia of Philosophy (SEP), it's said in Section 3.3 that Because of the finiteness of a natural number in contrast to, for example, a real number, many ...
I came across following problem to finding whether the following language is decidable or semi-decidable or not even a semi-decidable. $L: \{\langle M\rangle: M\space is\space a\space TM\space and\... 1answer 108 views ### Why is it not possible to prove that two Turing Machines calculate the same function? I was wondering why it is not possible. Is it because the corresponding language is not decidable, or because of the fact that it is not guaranteed that a Turing machine halts on every input? 2answers 43 views ### Busy-Beaver-like question for WHILE-Programs (Theoretical CS) So this is exam-task is called "Busy WHILE-Programs" In our lecture it was proven that WHILE-Programs are turing-complete. In short a WHILE-Program only allows the following: ... 0answers 231 views ### Proof by reduction and Turing machines [closed] This is a practice question I have, but I can't wrap my head around it. ............. Let L = {M | M is a TM that halts with exactly two words on its tape in the form Bw1Bw2B}. B = Blank Position the ... 0answers 60 views ### What Makes A TM undecidable (using Recursion Theorem) PROOF :We assume that Turing machine H decides ATM for the purpose of obtaining a contradiction. We construct the following machine B. B =“On input w: Obtain, via the recursion theorem, ... 0answers 16 views ### Given we restrict the time and memory allowed what bounds can we place on a halting decider? If a program is given as much memory and as much time to execute as it wants, then the halting problem is undecidable, and by Rice's theroem all non-trivial, semantic properties of programs like that ... 2answers 83 views ### Since the halting problem is undecidable, does that mean that there exists an always undecidable program? The usual demonstration of the halting problem's undecidability involves positing an adversarial machine (call it$A_0$) that runs the decider machine (call it$D_0$) on itself and performs the ... 1answer 143 views ### Variations of the halting problem Let$M$be an arbitrary Turing machine and$w \in \{0, 1\}^{*}$be a binary string. The language$\text{HALT} = \{\langle M, w \rangle : M ~\text{halts on input} ~w \}$is undecidable by the famous ... 3answers 289 views ### The Halting problem proof is wrong? First, let's see the pseudocode proof of halting problem: P(x) = run H(x, x) if H(x, x) answers "yes" loop forever else halt Then we have a ... 1answer 148 views ### Probabilistic halting problem I'm a physics and math student working through Nielsen & Chuang's text on quantum computation and information. I don't have much experience in CS theory, so some of these exercises are confusing ... 1answer 121 views ### Halting problem in C++ The halting problem relies on the fluidity of Turing machines. That is, a string can represent a machine. Can you do the same for C++ on a modern computer? Let's see my first attempt. Let ... 1answer 61 views ### Is halts-if-valid decideable? I have a suspicion that Turing's famous proof that the halting problem is undecidable may not prove exactly what people assume that it proves. It may only prove that it is possible to limit the ... 1answer 75 views ### Reduction to proof undecidability of the problem: machine M and N accept infinitely many words I am struggling with the following problem: Decide whether this problem is decidable or not: For two given Turing Machines M and N, there exists infinitely many words accepted by both machine M and ... 1answer 60 views ### How can I write a genetic programming algorithm, given that the Halting problem is unsolvable? I am learning genetic programming and to practice I want to write a simple algorithm which evolves a program that solves a simple function (say, square root). I intend to represent programs as ... 1answer 72 views ### How to prove the language of Turing machines that run at most$4|x|^2\$ steps is not recursive?
I am trying to prove that the language $$L=\{M\mid M\text{ is a TM and for all }x\in \Sigma^*\text{ with }|x|>2, M\text{ on }x\text{ runs at most }4|x|^2\text{ steps}\}$$ belongs to Co-RE but ...