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
1answer
38 views

Showing that the set of DTMs that run forever is not Turing-recognizable

The language A, that is all DTMS that run forever on input. Would this not just be the HALT problem? Therefore no reduction or proof is necessary, other then stating that? ANSWER FOUND: I think i ...
9
votes
5answers
3k views

Could the Halting Problem be “resolved” by escaping to a higher-level description of computation?

I've recently heard an interesting analogy which states that Turing's proof of the undecidability of the halting problem is very similar to Russell's barber paradox. So I got to wonder: ...
11
votes
5answers
299 views

Defining the halting problem for non-deterministic automata

The primary definition of Turing machine (TM), at least in my own reference textbook (Hopcroft+Ullman 1979) is deterministic. Hence my own understanding of the halting problem is primarily for ...
-4
votes
1answer
71 views

Set of Turing machines that halt after exactly 14 steps [closed]

Let $M_i$ be the Turing machine with Gödel number $i$. Let $$A = \{i \mid M_i \text{ with input \(x\) halts after exactly 14 steps}\}$$ Is the set $A$ recursive?
-3
votes
0answers
13 views

Theoretical Computer Science - halting issue? [duplicate]

Is the following set A recursive ?? M_i is a Turing machine by Gödel number i. A = {i |M_i with input x is halting exactly after 14 steps}.
19
votes
7answers
2k views

Is there a more intuitive proof of the halting problem's undecidability than diagonalization?

I understand the proof of the undecidability of the halting problem (given for example in Papadimitriou's textbook), based on diagonalization. While the proof is convincing (I understand each step of ...
0
votes
1answer
23 views

Decidable Problem

How should I go about showing that the following problem is decidable: Given DFAs M1 and M2, is L(M1) ⊆ L(M2)? What is the general strategy to prove ...
3
votes
1answer
24 views

Why is it true that the relation R and its negation are not semi decidable?

An example given for a relation R where its negation and itself are not semi-decidable was: $R(x,y)$ holds iff $y = 0$ then $R_{HALT}(x)$ holds, otherwise $y = 1$ and $R_{HALT}(x)$ does not hold. ...
0
votes
2answers
371 views

Turing Machine that computes maximum steps of halting machines

Suppose that $TM_{halting}$ is the set of machines that halt. Given a number of states $m$ and a length $n$ of the input, let $f(m,n)$ be the maximum number of steps a machine with $m$ states in ...
1
vote
1answer
41 views

Trying to understand the proof of the halting problem presented in Sipser textbook

I'm having some problems to understand the classic proof of the halting problem. The Proof: $A_{tm} = ${$<M,w>$ | $M$ is a $TM$ and $M$ accepts $w$}. We assume that $A_{tm}$ is decidable and ...
0
votes
1answer
87 views

Halting problem reduction to Halting for all inputs

I was going through my book of revision and I would like someone hints on this. The Halt for All Input problem (HAI) takes a machine and tell if this machine halts or not for any input We prove it ...
0
votes
1answer
123 views

Halting problem reducing to the blank tape halting problem

I was going through my book of proof and I find very confusing its definition, so I would like someone to help me in understanding this. The blank tape problem takes a machine and an empty tape and ...
3
votes
2answers
97 views

Halting Problem and Turing Degree and Reduction? [closed]

This is a Local Olympiad question on computation and computer science on 2013. How can explain it and says some hint for understanding such an example question. for $ A \subseteq \mathbb{N}$ we ...
1
vote
2answers
71 views

About being able to sample a permutation of a finite set uniformly at random [closed]

I was looking at this question. So if I understand the above discussion right then it concludes that if say one had access to an oracle which can uniformly at random sample from a finite set then ...
0
votes
1answer
75 views

Does Church's Thesis include artificial intelligence?

By Church's Thesis it is impossible to design an algorithm to decide halting problem. I would like to know the word algorithm in this context includes artificial intelligence or not? I mean is it ...
0
votes
0answers
37 views

Turing's solution to the Entscheidungsproblem [duplicate]

Based on what I have read so far, to me it sounds like Alan Turing's solution the Entscheidungsproblem means that there is no algorithmic solution to tell whether a given algorithm with input will ...
1
vote
1answer
200 views

Why can't we solve the Halting Problem by using Artificial Intelligence? [duplicate]

Yesterday I was reading about Computability and they mention the Halting Problem. It got stuck in mind all day until I remember that some weeks ago, when learning Java, the IDE (Netbeans) show me a ...
1
vote
0answers
113 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
1k 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
51 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
56 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
221 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
97 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
65 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
224 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 ...
2
votes
1answer
99 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
41 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 ...
74
votes
10answers
17k 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 ...
2
votes
3answers
103 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
40 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
82 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
91 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
106 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
468 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
72 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
314 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
57 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
187 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
98 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
56 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
77 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. ...
4
votes
3answers
503 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
252 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
1k 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 ...
20
votes
6answers
1k 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
44 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
153 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
88 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
67 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 ...