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

learn more… | top users | synonyms

-4
votes
0answers
16 views

Is a union of any TM language and the halting problem language decidable [duplicate]

I need to find if the following language is decidable (in $R$): $L=\{ \langle M \rangle \mid M \text{ is a TM}, L(M)\cup H_{TM}\in RE\}$ Where $H_{TM}$ is of the halting problem. My intuition is ...
2
votes
1answer
61 views

Does the Halting Problem prove that true Artificial Intelligence is impossible?

The Halting Problem demonstrates that there are things that a machine can never be programmed to do. Is this proof that true Artificial Intelligence - that is, the ability for a machine to think and ...
1
vote
0answers
41 views

Is $f$ which returns the $n$-th word in $\overline{H_{TM,\epsilon}}$ computable?

The question itself: Let $f:\mathbb{N}\to\Sigma^\star$ be such that $f(n)$ returns the $n$-th word in $\overline{H_{TM,\epsilon}}$ (which is the complement of the language of TMs which accept ...
3
votes
1answer
36 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 ...
1
vote
1answer
44 views

A question about halt (or stop) of Turing machine

I try to understand something: At Turing machine we have two stats: $q_{accept}$ and $q_{reject}$. Now, if machine $M$ runs on word $w$ (I hope I write it right...) and the final configuration is: ...
0
votes
1answer
50 views

Axioms - proof of halt

I am new to this forum and this is my first post. I am interested in solving a problem, but cannot find the way to think about it. If anyone can guide me through it, I would be obliged: Let F be some ...
1
vote
1answer
32 views

Removing $\epsilon$ transitions in a NPDA

NPDA's and general NFA's may not halt for finite inputs like DFA's do because of their $\epsilon$ transitions. However, NFA's with $\epsilon$ transitions could be converted to those without any ...
7
votes
2answers
1k 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 ...
7
votes
3answers
790 views

Undecidability of telling if a program returns true or false

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 ...
1
vote
2answers
70 views

What does it mean to be Turing reducible?

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 ...
3
votes
1answer
266 views

Show that the Halting problem is reducible to its complement

HALT$_{TM}$ is the set of all machine-input pairs $<M,w> $ where $M$ halts on input $w$ The complement of HALT$_{TM}$ is the set of all machine-input pairs $<M,w> $ where $M$ ...
1
vote
0answers
15 views

IsDefined predicate computable?

I am working on a computability assignment, I want to define a helper predicate IsDefined by: $IsDefinied(x,n) = \{ 1$ if $\Phi^{(1)}(x,n)$ is defined, $0$ otherwise. Where $\Phi^{(1)}$ is the ...
1
vote
1answer
139 views

Proof by Reduction: From Empty Language to Halting Problem on Empty Input

Question: Let language $E$ = {$\langle M \rangle$ | $M$ accepts no inputs whatsoever} Let language $H$ = { $\langle M \rangle$ | $M$ halts on an empty string input}. Is it possible to show that $H$ ...
0
votes
2answers
199 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 ...
1
vote
1answer
65 views

Blank tape halting problem vs. Emptiness problem ($H_0$ vs. $E_{TM}$)

I have difficulties to differentiate the $H_0$ from the $E_{TM}$ problem. What exactly means $L(M)= \emptyset $? Is it dffierent from $input~ \varepsilon$ or is $L(M)= \emptyset \leftrightarrow ...
9
votes
1answer
250 views

Is the halting problem decidable for 3 symbol one dimensional cellular automata?

I've been trying to figure out if the halting problem is decidable for 3-symbol one-dimensional cellular automata. Definition Let $f(w,i)$ denote the configuration of the system at time step $i$. ...
2
votes
1answer
53 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 ...
2
votes
0answers
33 views

What language features would I need to remove from a real programming language to make it decidable? [closed]

Let's say that I want to restrict certain features of a common programming language--for instance, C--such that the result is decidable, and thus no longer Turing-complete. What language features, at ...
1
vote
2answers
63 views

Why does the proof of undecidability of $A_{TM}$ require the universal TM to take input $\langle M,\langle M\rangle\rangle$?

I've read a proof explaining why $A_{\mathrm{TM}}$ is undecidable, and I don't seem to understand why we need to give the opposite of $H$ function $D$ itself as input. Here's the copy-paste of that ...
1
vote
2answers
88 views

Can we enumerate provably non-terminating functions?

In trying to understand the Halting Problem better, I am trying to come up with classes of provably non-terminating programs. For example, any program (including input) which leads to a ...
0
votes
0answers
21 views

Difficulty in the halting problem for a simple Turing machine with standard enumerations of programs and of initial tape configurations

Preparations Consider a Turing machine with just one head and one tape (on which the head may move left, move right, or remain stationary), and with just two symbols ("blank" and "non-blank"). The ...
0
votes
0answers
40 views

What can be said about the Halting Problem if we can include the halting status to the input?

I was reading about Turing Machines and the Halting Problem, i understand that you need an oracle to decide whether given input will halt or loop forever. But why do we need an oracle if we can ...
3
votes
1answer
52 views

The halting problem of Turing machines in view of enumeration of initial tape configurations

As far as I know, presentations of the (general) halting problem (cmp. Wikipedia) are referring explicitly to an ennumeration of (applicable) programs. For the purpose of my questions let's consider ...
1
vote
2answers
367 views

Is how much memory a program needs computable?

We know that how much time a program needs is not computable. Do we know how much memory a program needs is decidable?
0
votes
1answer
47 views

Understanding the proof of the halting problem [closed]

I came across the following example that proves that the blank tape halting problem is not decidable. I understand the proof technique, but I just don't see how the blank tape problem is shown to ...
8
votes
3answers
657 views

Halting problem - one issue that's bothering me

To my knowledge, halting problem asks if there exists a program that decides whether a program being tested, given some input data (no matter what program it is, or what input data we give) will ...
2
votes
1answer
60 views

Can we use a different encoding scheme to solve an unsolvable language?

Say we have a particular decision problem and that we have an alphabet and an encoding scheme, which gives us a language L that we say is not recursive (i.e. we do not have a Turing Machine that can ...
2
votes
1answer
241 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 ...
1
vote
0answers
37 views

Is the halting problem a matter of an encoding scheme ?

I was reading about the halting problem recently, there is a video on youtube where it tries to explain the halting problem easily (since it is complicated to explain). So, (A,C & H) have ...
5
votes
2answers
3k views

Why won't a Turing machine halt?

I am reading Sipsers. The book introduces halting problem and proves that is a turing recognisable language but not a turing decidable language. Thus giving a Turing machine which does not halt on ...
1
vote
2answers
74 views

What's the error in the following proof of the halting problem decidability?

Let's encode every state and tape word (with position of Turing machine on it) with a single integer. Then the transition function can be represented as a total function from integers to themselves. ...
12
votes
6answers
4k 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. ...
0
votes
1answer
46 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 ...
13
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: ...
12
votes
5answers
524 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 ...
-3
votes
1answer
82 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?
23
votes
7answers
3k 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
34 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
33 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
441 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
56 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
555 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
2k 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
122 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
102 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
124 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
82 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
738 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 ...
2
votes
1answer
666 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 ...