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

learn more… | top users | synonyms

0
votes
0answers
46 views

Is the language of Turing Machines that halt on every input recognizable?

I am trying to reduce the complement of the HALTING problem (WLOG, the complement of the HALTING problem is the language of TMs that loop on some string w)to this language in order to show that it is ...
7
votes
3answers
974 views

Does the proof of undecidability of the Halting Problem cheat by reversing results?

I have trouble understanding Turing's halting problem. His proof assumes that there exists a magical machine $H$ which could determine whether a computer would halt or loop forever for a given input. ...
0
votes
1answer
42 views

Why Halting problem is Recursively Enumerable?

If we take this definition as R.E. set definition (Computability, Complexity and Languages book written by Davis in page 79) $Definition.$The set $B\subseteq N$ ...
1
vote
1answer
32 views

Is Universality Theorem applicable to Halting problem? [closed]

This is Universality theorem In the Computability, Complexity and Languages book written by Davis in page 70: If $\phi^{(n)}(x_1,...,x_n,y) = ...
3
votes
1answer
187 views

What is the exact meaning of a Predicate, decidability and computability?

In the Computability, Complexity and Languages book written by Davis in page 5 he defines a predicate as: By a predicate or a Boolean-valued function on a set ...
-2
votes
1answer
88 views

A proof that P != NP [closed]

I came up with the following. Am I doing something wrong? Suppose $P=NP$. Let $A$ be an NP hard problem. Let $A'$ be the polynomial reduction of $A$. By the assumtions, the Halting problem holts for ...
17
votes
2answers
1k views

Are there programs that never halt and have no non-termination proof?

Like black holes in computer science. We can only know they exist but when we have one of them we will never know it's one of them.
1
vote
1answer
39 views

Proving a function is uncomputable [duplicate]

I am trying to solve the following problem: For each Turing machine $M_k$ and each string $x$ in $\{$0,1$\}$$^\ast$ let $time_k(x)$ = $\{$the number of steps executed by $M_k(x)$ if ...
5
votes
1answer
215 views

How a reduction can help up solve a problem?

I am studying the basics of Computation Theory and I came up with an example I can't understand. Let's have a language $L = \{\langle M\rangle \mid L(M) = \Sigma^{\ast} \}$, so $L$ contains codes of ...
1
vote
1answer
64 views

If the Halting Problem was solvable, and we solved it, what would be its implications?

Perhaps a way to better understand the Halting Problem's importance is to know what would happen or what could be possible if this was solved. What would be the Halting Problem's implications in ...
-1
votes
1answer
32 views

Why apply the assumed decide für HALT to the input and its code?

In the lecture notes I have got in class I have the following proof for the halting problem not being recursive Assume $H$ is recursive and TM $M_1$ decides it. Construct $M_2$ that gets ...
65
votes
10answers
13k views

Why, really, is the Halting Problem 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 ...
2
votes
3answers
90 views

Is $AlwaysHalt$ recursively enumerable?

I was doing some complexity theory exercices and I came over this one: $AlwaysHalt = \{R(M) | M$ halts with all $x \in \{0,1\}^*\}$ Is $AlwaysHalt$ recursively enumerable? I would say YES and ...
1
vote
1answer
36 views

Is $K' = \{ w \in \{0,1\}^* | M_w$ Halts on $w \}$, where $M_w$ is the TM whose encoding is $w$, equivalent to the halting problem?

My professor presented the halting problem as $K' = \{ w \in \{0, 1\}^* | M_w$ Halts on $w \}$, where $M_w$ is the TM whose encoding is $w$ (i.e. $w = \langle M \rangle$), and said it was equivalent ...
2
votes
1answer
75 views

Is there a class of formal grammars that generate Recursive Languages only?

Is there a class of formal grammars that generate Recursive Languages only? (ie with which it is not possible to generate non recursive languages.) If so what kind of production rules/restrictions do ...
2
votes
1answer
79 views

Decide if a specific Turing machine halts on a specific string

Can you always decide if a specific Turing machine accepts a specific string? I started thinking about this after reading an answer to this question, Rice's theorem vs Turing completeness, which ...
2
votes
2answers
103 views

Known lower bounds on halting for finite machines?

It's possible to determine whether a deterministic machine with finite memory will halt in O(n) time if the machine has n possible states. You simply run the machine until it halts or visits the same ...
4
votes
7answers
413 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 ...
2
votes
1answer
59 views

Smallest non-halting unlambda program

Is ```sii``sii the smallest Unlambda program that doesn't halt? In other words, what is the smallest non-terminating combinator term in SKI augmented with $C$ ...
5
votes
2answers
251 views

Halting problem without self-reference

In the halting problem, we are interested if there is a Turing machine $T$ that can tell whether a given Turing machine $M$ halts or not on a given input $i$. Usually, the proof starts assuming such a ...
3
votes
1answer
50 views

Is there an undecidable decision problem that computable algorithm for it leads to an algorithm for halting problem?

Suppose, to the contrary, that there exists a computable algorithm for some undecidable decision problem. Would this mean that halting problem would be solved by a computable algorithm? I know that ...
-1
votes
3answers
151 views

If Halting problem is decidable, are all RE languages decidable? [closed]

Assume the halting problem was decidable. Is then every recursively enumerable languagerecursive?
3
votes
1answer
73 views

The proportion of halting programs vs non-halting programs, of decidable programs vs undecidable languages

Can the following two statistics be bounded: the proportion of halting programs vs non-halting programs the proportion of decidable vs undecidable languages For example, can we say that one class ...
1
vote
1answer
43 views

Examples for incomparable semi-decidable but undecidable languages

In Schönig and Pruim's Gems of Theoretical Computer Science, the following statement is made: 'Post's Problem', as it has come to be known, is the question of whether there exist undecidable, ...
0
votes
1answer
66 views

Why is $A_{TM}$ reducible to $HALT_{TM}$?

In Sipser, there is a proof I don't understand. First he established the undecidability of $A_\mathrm{TM}$, the problem of determining whether a Turing machine accepts a given input. ...
3
votes
3answers
306 views

Are all undecidable/uncomputable problems reducible to the Halting problem? [duplicate]

Theory of computation tells us that there are some languages that cannot be recognized by a Turing machine. That is, there are well-defined problems for which no Turing machines can provide an ...
5
votes
1answer
211 views

Are there any existing problems that wouldn't be solvable with a halting oracle?

I understand that most problems are trivial if a halting oracle is available (or, I think equivalently, hyper-computation). However, applying the argument that shows the Halting Problem is impossible ...
8
votes
3answers
969 views

Gödels (first) incompleteness Theorem and the Halting Problem - How limiting is it?

When I first heard of these things I was very fascinated as I thought it sets really a limit to mathematics and science in general. But how practically relevant are these things? For the Halting ...
19
votes
6answers
992 views

Is there a connection between the halting problem and thermodynamic entropy?

Alan Turing proposed a model for a machine (the Turing Machine, TM) which computes (numbers, functions, etc.) and proved the Halting Theorem. A TM is an abstract concept of a machine (or engine if ...
1
vote
0answers
34 views

Undecidability instance on a “find a proof/disproof” machine

I'm following through the proof of the impossibility of the Halting problem for the umpteenth time. It all makes sense logically, but not intuitively. A question I got stuck on: Suppose we built the ...
8
votes
1answer
124 views

Hilbert's 10th Problem and Chaitin's Diophantine Equation “Computer”?

In Chaitin's Meta Math! The Quest For Omega, he briefly talks about Hilbert's 10th Problem. He then says that any Diophantine Equation $p=0$ can be changed into two equal polynomials with positive ...
3
votes
1answer
84 views

Is there a largest class of halting programs?

The halting problem says that a Turing machine cannot decide if another Turing machine halts. However, we know that it is possible to determine if some programs halt. For example, FORTRAN DO ...
0
votes
1answer
62 views

How can a problem be undecidable yet enumerable? [duplicate]

How can something be enumerable but be un-decidable ie, this states the halting set is un-decidable and enumerable. Enumerable means it can be computed, ie has the same cardinality as natural numbers ...
0
votes
0answers
42 views

Does the head of TM M ever move into cell x when processing Input I?

The question is whether this is recursive or not. I first thought that it wasn't but then I read this question which seems similar and is recursive. Is it decidable whether a TM reaches some position ...
0
votes
1answer
147 views

Turing machines and languages — recursive (enumerable) or not

For an assignment in my university, we have to answer multiple choice questions about theoretical computer science. This particular one I find very hard to understand. I wonder if some of you could ...
5
votes
2answers
600 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 ...
0
votes
1answer
76 views

Regarding Turing Machine Halting Problem [closed]

All problems solved by standard today's general purpose computer can be solved by standard Turing machine.As general purpose computer can't do more than Turing machine so The Turing machine halting ...
5
votes
1answer
88 views

Possible to construct a probabilistic halting problem solver?

I'm a CS undergrad so my math/CS knowledge is not that deep so please correct me if my premise is flawed or I have made some incorrect assumptions. So I was thinking, much in the way that some ...
2
votes
2answers
541 views

Why is the halting problem unsolvable by a turing machine? [duplicate]

So my knowledge of CS is amateurish at best but to me, logically, it seems like the halting problem is solvable. So any human can determine if a problem halts with rigorous inspection, so why can't a ...
2
votes
1answer
201 views

Trying to break the proof of undecidability of the halting problem

Posted this question on cstheory.SE where they said to go here: I read the demonstration of the Halting problem, it is done by reductio ad absurdum where the push to get to the absurd is to use ...
4
votes
1answer
202 views

Is the halting problem specific to Turing machines?

The proofs that the halting problem is undecidable seem to make very few assumptions about the kind of program/machine under consideration: just that the programs take one input and either loop or ...
2
votes
2answers
88 views

How to prove that “Total” is not recursive (decidable)

$\mathrm{Halt} = \{ (f,x) | f(x)\downarrow \}$ is r.e. (semi-decidable) but undecidable. $\mathrm{Total} = \{ f | \forall x f(x)\downarrow \}$ is not r.e. (not even semi-decidable). I need some help ...
8
votes
3answers
286 views

Is there a TM that halts on all inputs but that property is not provable?

Does there exist a Turing machine that halts on all inputs but that property is not provable for some reason? I am wondering if this question has been studied. Note, "unprovable" could mean a ...
3
votes
2answers
116 views

Can a method be written if the language is undecidable?

If a language is decidable, we can write a method that always halts and returns true for each string that is an element of the language and ...
1
vote
1answer
104 views

Confusing equivalence $\Phi(n,n)\downarrow \Leftrightarrow \text{HALT}(n,n)$

Let $B$ be a recursive enumerable set and $B = W_n$, where $W_n = \{x \in \mathbb N \mid \Phi(x,n)\downarrow\}$ and $\Phi^{(n)}(x_1, \ldots, x_n, y)$ is the value of the function at the terminal ...
2
votes
2answers
113 views

Alternative proof for the undecidability of $A_{TM}$

The proof of the undecidability of $A_{TM}$ in Michael Sipser's textbook* contains the definition of a Turing Machine, which accepts the encoding of a TM, if this ...
1
vote
2answers
233 views

Is oracle computer capable of doing infinite loops?

Solve this problem: "build an infinite binary oscilator" With a Turing Machine we can solve it a=False While True: a=not a print a, then output will be ...
1
vote
1answer
171 views

Can a Turing machine decide if a LOOP program stops for the integer input 0

This is a question I found in a practice exam while I am preparing for my mid term exam. The answer needs justification, either a pseudo code or a logical explanation why not. What puzzled me about ...
4
votes
1answer
897 views

Relationship between Undecidable Problems and Recursively Enumerable languages

I have read the Wikipedia article on Recursively Enumerable languages. The article suggests that the halting problem is recursively enumerable but undecidable. My idea till today was that the halting ...
3
votes
1answer
109 views

Halting problem

I have some concerns about the Halting problem. This is the proof I know: Let $h(M, i)$ be a function, $M$ being Turing machine and $i$ input for the Turing machine. Let $h(M, i)$ output true ...