Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [halting-problem]

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

4
votes
2answers
36 views

Can every Turing Machine be translated into a SAT formula?

For the proof of "Cook-Levin Theorem", for a Turing Machine $M$ that accepts a language $L \in NP$ and input $x \in \{0,1\}^*$, we can create a SAT Formula, that is satisfiable if and only if $M$ ...
1
vote
1answer
61 views

Is the halting problem solvable for NPDAs?

After the total silence in response to my last question, I am rethinking my assumptions. DPDAs are, of course, solvable, and I believe that their loops can be found in the manner I described in my ...
2
votes
1answer
45 views

Show that the following language is undecidable

$\{ M \mid M \text{ is a machine that runs in }100n^3 + 300\text{ time }\}$ I am currently stuck with this one. I thought of reducing HALT to M as the reduction seems legitimate to me: if the first ...
2
votes
1answer
25 views

Computability: Proving a predicate is not recursively enumerable

Let P(p) <=> for each x, comp(p,x) is defined. Can anyone explain to me how to prove that P is not RE (recursively enumerable) ?
2
votes
0answers
67 views

Detecting loops in NPDAs

I'm aware that the halting problem is solvable for PDAs, but I have recently discovered that I am wrong about how to actually do it. I used to think that you could detect an infinite loop by meeting ...
0
votes
1answer
42 views

Define the following problem as a language and prove that it is undecidable with a reduction from the halting problem.

...Knowing whether a Turing machine will ever output your name on the tape. The language is the set of all TMs that print your name. Reduce from HALT TM. I had this problem on my exam. From my ...
13
votes
3answers
4k views

Why is the halting problem decidable for LBA?

I have read in Wikipedia and some other texts that The halting problem is [...] decidable for linear bounded automata (LBAs) [and] deterministic machines with finite memory. But earlier it is ...
-1
votes
1answer
53 views

Does solving all Halting problem instances 'in the limit' imply we solve an undecidable problem?

The recent Arxiv paper "Learning the undecidable from networked systems" attempts to construct a network of $N$ Turing machines$^1$ that can solve the Halting problem for any program of size $O(\log N)...
8
votes
1answer
522 views

Does Church-Turing thesis also apply to artificial intelligence?

By Church-Turing's thesis, it is impossible to design an algorithm to decide the halting problem. Does the word algorithm in this context include artificial intelligence or not, that is, does ...
2
votes
3answers
186 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 ...
3
votes
2answers
69 views

Enumerate over all halting Turing Machines?

I understand that it is possible to enumerate over all Turing Machines. My understanding of how this works is by fixing an encoding of natural numbers to TM descriptions, and then enumerating the ...
0
votes
2answers
89 views

Can we enumerate finite sequences which have no halting continuation?

Note: this question has been cross-posted to Math.SE, after about a week here. I am trying to deepen my understanding of the relationship between the Halting Problem and Godel's Completeness Theorem (...
1
vote
1answer
115 views

Counter Machine (Halting Problem)

How can we show that Halting Problem for one-counter additive machines is decidable ?
1
vote
1answer
47 views

Halting Problem, Typed Version: A Headache

After many years, I have been revisiting the venerable old Halting Problem and the self-referential / diagonalization “party trick” that shows that there is no Turing Machine able to solve it. I was ...
7
votes
6answers
985 views

How is Turing's Solution to the Halting Problem Not Simply “Failure By Design”?

I'm having a hard time viewing Turing's solution to the Halting Problem as a logician, rather than as an engineer. Here is my understanding of the Halting Problem: Let $M$ be the set of all ...
0
votes
1answer
60 views

Would Schmidhuber's theories of everything be capable of performing hypercomputation?

Jürgen Schmidhuber pointed out that a simple explanation of the universe would be a Turing machine analogy programmed to execute all possible programs computing all possible histories for all types of ...
2
votes
2answers
86 views

Is determining if a Turing machine runs in constant time decidable if one assumes it halts?

As the title states, is determining if a Turing machine runs in constant time decidable if one assumes it halts? The decision problem, more formally: Given a Turing machine $M$ where it is assumed ...
0
votes
1answer
171 views

Prove that there exists a machine which decides an infinite subset of halting problem

We already know that $H:=\{\langle M,w\rangle | M$ halts on $w\}$ is undecidable, then how can there possibly be a machine that decides any infinite subset of $H$?
2
votes
3answers
1k views

Halting problem without input?

I'm only a layman therefore only discuss stuff naïvely. I read some introductory articles about halting problems with a scenario that if there were such a decider accessible to us, we should be able ...
0
votes
1answer
74 views

Why a TM with infinite states can decide the halting problem?

Assuming we have a model of TM with an infinite number of states. The domain and range of the transition function are also infinite. Given a description of a TM $M$ and a string $w$ how can we use the ...
1
vote
0answers
33 views

How to create model for a powerful language whose programs are guaranteed to terminate?

I'm creating a powerful regular expression matching system that can be augmented by adding small microprograms to deterministic finite automaton (DFA) states. The microprogram solves the big bang ...
1
vote
2answers
102 views

Recognizer for decidable language and words it doesn't halt on

Suppose we have a decidable language B (there exists some TM that decides it). Suppose we have another TM M which only ...
9
votes
2answers
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 ...
0
votes
1answer
59 views

Is this language recognizable?

Let $L = \{M: M\text{ halts on only one of 1100 or 0011 or 0011 or 1000}\}$. I'm trying to determine whether $L$ is decidable. I don't think it's even recognizable, but I'm not sure. Regardless, I ...
1
vote
1answer
102 views

How to prove that a problem is undecidable by using the Halting problem?

I cannot understand how to reduce the halting problem to a property to show that is undecidable. For example, I have this property of a Turing Machine and I have to prove if it's recursive or not: "...
0
votes
1answer
54 views

Halting problem with extra input

Can there be a function HALT(f, y) so that: There are some x such that f(x) halts iff there ...
3
votes
2answers
416 views

With a halting oracle, can tell whether something will have finite output?

A program can have finite output, yet still not halt. Example: 1: output "Yolo" 2: output "" 3: go to step 2 This only ever outputs "Yolo", despite never halting....
4
votes
2answers
101 views

Converse of halting problem

It is well known that if some computing apparatus is Turing-complete, then the halting problem is undecidable for that computing apparatus. However, is it true that if the halting problem is ...
3
votes
2answers
110 views

Is it possible to write a program that calculates an algorithm's time complexity? [duplicate]

Title is self explanatory. I have searched here on this site and haven't found any discussion about this. Is it somehow related to Turing's Halting problem (which is undecidable)?
58
votes
10answers
9k views

Human computing power: Can humans decide the halting problem on Turing Machines?

We know the halting problem (on Turing Machines) is undecidable for Turing Machines. Is there some research into how well the human mind can deal with this problem, possibly aided by Turing Machines ...
1
vote
1answer
72 views

Turing decider Halting Problem

Wiki and my classes Textbook defines a decider as: In computability theory, a machine that always halts—also called a decider (Sipser, 1996) or a total Turing machine (Kozen, 1997)—is a Turing ...
141
votes
11answers
48k views

Why, really, is the Halting Problem so important?

I don't understand why the Halting Problem is so often used to dismiss the possibility of determining whether a program halts. The Wikipedia article correctly explains that a deterministic machine ...
3
votes
2answers
139 views

Does Halts reduce to all other undecidable languages?

In a CS theory class I'm taking, we showed Halts was undecidable via a diagonalization argument. All other undecidable problems we looked at we either got by reducing Halts to them, or some chain of ...
1
vote
0answers
93 views

Prove that $H$ reduces to $H\varepsilon$

I have to prove that $H_\varepsilon = \{<M> \mid M\ \text{halts on input }\varepsilon\}$ reduces to $H$ (the halting problem). I am very confused how to PROVE it, I mean it is clear that we can ...
27
votes
7answers
6k views

What are the simplest examples of programs that we do not know whether they terminate?

The halting problem states there is no algorithm that will determine if a given program halts. As a consequence, there should be programs about which we can not tell whether they terminate or not. ...
2
votes
2answers
80 views

Why did Alan Turing have to define computation before demonstrating undecidability?

It seems to me that Turing could've just presented the following argument: Theorem: Given a computational model $\mathcal{M}$ capable of conditional branching and indeterminate repetition the halting ...
1
vote
1answer
156 views

Prove if a property of a Turing Machine is decidable or not, how can I do it?

I cannot understand how to prove if a certain property of a Turing Machine M is decidable or not. For example, if a have this: (1.1) "M always halts within 100 steps" or this (1.2) "M recognizes ...
1
vote
0answers
23 views

Is there an impossibility to mechanically distinguish between sets and classes?

Assuming only computable functions, and in line with set theory, defining a "proper class" as a collection that is itself not allowed to be a member of a set. A "collection" is then defined as either ...
1
vote
1answer
23 views

does there exist for each program that produces a sequence, a program that returns true or false if a number is in the sequence?

let S be the set of all programs that take a natural number as input and return another natural as output. let M be the set of all programs that take a natural number as input and return true or false....
-3
votes
1answer
310 views

Is Alan Turing's proof of the incomputability of halting problem invalid?

I fail to see a contradiction in the halting machine proposed by Alan Turing. Definition of halting machine Where H = all possible programs that terminates N = all possible programs that do not ...
1
vote
1answer
173 views

A reduction of $HALT_{TM}$ to $A_{TM}$

A widely used example of reductions, is a reduction of $A_{TM}$ to $HALT_{TM}$. How to show the opposite reduction, meaning of $HALT_{TM}$ to $A_{TM}$, if possible.
0
votes
2answers
197 views

Prove or disprove if $L_{1}$ is undecidable and $L_{2}$ is finite language then $L_{1} \cup L_{2}$ is undecidable

I tried to prove by contradiction. $L_{1}$ is undecidable and $L_{2}$ is finite language then $\overline{L_{1}}\cap \overline{L_{2}}$ is decidable. $$L_{1} = \overline{HALT_{TM}} = \big\{ \langle M, ...
2
votes
3answers
4k views

Understanding proof for Busy Beaver being uncomputable

I found this proof on http://jeremykun.com/2012/02/08/busy-beavers-and-the-quest-for-big-numbers/ and have highlighted the part I don't understand in bold. (BB(n) is defined as the number of steps ...
8
votes
2answers
709 views

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

I'm trying to find a way to explain the idea of the Halting Problem proof in as accessible a manner as possible (to undergrad CS students). The simplest argument I have found is this one; this is ...
3
votes
1answer
417 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 ...
4
votes
1answer
71 views

if an argument of a lambda only passes itself if it is further evaluated, is runtime always finite?

In order for a lambda expression to run forever, there must be at least one lambda in the expression in which an argument is passed to itself. For example the following runs forever. $$ (\lambda x.xx)...
0
votes
0answers
37 views

Reduction of HP to L3

I want to make the following reduction: HP is the Halting Problem: HP = {w#x | w, x ∈ {0,1}* , Mw halts on input x} w is the binary coded turing machine Mw. L3 is the problem which asks, if M ...
2
votes
1answer
77 views

What is the current state of the art in solving the halting problem? [closed]

Yes, I know it's uncomputable in the general case. What I want to know is what special cases have been solved, and if there is work ongoing on finding or developing more of them. To be a little more ...
1
vote
2answers
49 views

Does the undecidability of the halting problem require Turing Machines to be enumerable?

I (think I) understand the enumeration and then diagonalization proof of the undecidability of the halting problem, but I came cross this proof in SICP below, which does not seem to require the ...
3
votes
1answer
445 views

Can a weaker version of the Halting Problem be solved?

I've been learning about the Halting Problem and the proof that it is undecidable in its general case. The proof that it cannot be solved generally goes something like this: Assume that some machine $...