Questions tagged [halting-problem]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
98 views

Showing $1$-reducibility of $\overline{\text{HALT}'}$ to index set

Note: overline denotes complement I am trying to show that $\overline{\text{HALT}'}\leq_1 \{i\colon\Phi_i=\Phi_e\}:= A$ for some fixed $e$ but I am misunderstanding the problem or method and can't ...
0
votes
3answers
477 views

What Turing's proof of Halting Problem really proves?

This is something that has bugged me for a while, so I hope you can help me. Suppose: $A'$ is the set of all programs, $halt?$ is the halting problem solver, $D$ is the program that is constructed ...
3
votes
1answer
430 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 ...
1
vote
1answer
726 views

Which Turing machine problems are Decidable?

Let $M_0$, $M_1$, $M_2$,..., be an effective enumeration of all Turing machines. Which of the following problems is (are) decidable ? Given a natural number $N$, does $M_N$ starting with an empty ...
6
votes
1answer
192 views

Is there any demonstrably uncomputable concrete problem which does not rely on diagonalization?

So diagonalization as we all know is an extremely productive way of showing uncomputability, the other main tool used by CS people for this task being reduction. But it has occurred to me that I do ...
1
vote
0answers
59 views

Reducing Halting Problem to Acceptor for TM

We have $A_{TM}=\{(M,w)|M$ is a TM, $w\in \Sigma^*_{TM},M$ accepts $w\}$ We intend to show that $HALT(M,w)\leq_T A_{TM}$ i.e. if we are given a machine for $A_{TM}$, we can decide whether $M$ halts ...
0
votes
0answers
26 views

How did Turing prove that there is no general process to determine whether a Turing Machine is unsatisfactory?

In the book The Annotated Turing, Charles Pezold writes: Because Turing Machines are entirely defined by a Description Number, it might be possible to create a Turing Machine that analyzes these ...
1
vote
1answer
326 views

Under which operations is the class of non-recursive languages a closure?

I am currently studying turing computability and related problems such as the halting problem with a background in formal languages. I know that the class of recursive (decidable) languages is a ...
3
votes
1answer
96 views

Can we prove that a time machine is impossible using the Halting Problem?

Let us take a hypothetical machine i which halts on the ith day of the month if it rains on the ...
1
vote
0answers
17 views

Is there evidence to suggest Macsyma was directed at the Diophantine equations in the Entscheidungsproblem?

I'm reading the book The Annotated Turing by Charles Petzold. In it he mentions the Diophantine equations - which was a joy to read. This then lead to Hilbert's 10th problem - finding an algorithm ...
3
votes
1answer
196 views

Is there any way to get “around” the halting problem?

As I understand it, one proof of the Halting Theorem is done by contradiction; we assume we have program X which can determine if any program terminates. We input program X into program X (with some ...
0
votes
1answer
416 views

Explanation of an explanation of Turing's proof to the halting problem?

I am reading the transcription of a lecture from a professor Scott Aaronson, specifically the section titled Turing Machines. In this section he describes Turing's proof of the Halting Problem. But ...
1
vote
1answer
90 views

Is this padded version of the Halting Problem in NP?

I'm using the following definition of $NP$: $$A \in NP \Longleftrightarrow A(x) = \exists w: B(x,w) $$ where $B \in P$ and $|w| = poly(|x|)$. Now instead of the problem whether the program $\Pi$ ...
2
votes
1answer
112 views

How does the halting theorem interact with the recursion theorem?

Recursion theorem (paraphrasing Sipser, Introduction to the Theory of Computation): Let T be a program that computes a function t: N x N --> N. There is a program R that computes a function r: N --> ...
8
votes
2answers
360 views

Chaitin's constant is normal?

According to this source, Chaitin's constant $\Omega$ is normal. Each halting probability is a normal and transcendental real number that is not computable, which means that there is no algorithm ...
1
vote
0answers
221 views

Mapping reduction from $A_{TM}$ exercise

Let $L = \{\langle M \rangle \mid \text{M is a TM which accepts only the string "010"}\}$. Prove that $L$ is undecidable. This is my solution, reducing $A_{TM}$ to $L$: $R(\langle M,w \rangle)$ ...
0
votes
1answer
64 views

Are there algorithms for which we cannot determine if they ever halt? [duplicate]

My understanding of the halting problem in layman's terms is that there is no algorithm which will accept an arbitrary program as input and return true if it halts and false if it does not. For a ...
2
votes
1answer
193 views

How do we know that the reduction is correct?

I'm having a really difficult time understanding the logic behind reduction of the halting problems to other problems in order to prove them undecidable. Here's my reasoning: Let's say that we want ...
1
vote
1answer
82 views

Given a Turing Machine M and a string $x$ how do we tell whether a the Turing Machine M loops on the string $x$

Let us say there is a Turing Machine $M$ and a string $x$. So now I want to know if $M$ accepts or rejects the string or loops on it. So, I feed the string to $M$. So, if $M$ is accept or reject the ...
1
vote
1answer
278 views

Is a language of some deciders decidable?

Is $$L = \{ \langle M \rangle \mid M = (\{Q_1, Q_2, . . . , Q_{100}\}, \{0, 1\}, \{0, 1, \_\}, δ, Q_1, Q_2, Q_3) \text{ is a decider}\}$$ decidable? I know $$HALT_{TM}= \{ \langle M \rangle \...
0
votes
1answer
129 views

Turing machine for which it is impossible to decide if it halts?

Assuming someone tries to approximate a function which decides if a turing machine halts or not. It uses only a finite amount of time. The function returns $0$ (=the turing machine halts), $1$ (=the ...
1
vote
3answers
200 views

What is the meaning and significance of a Turing machine taking a description of itself as input?

Currently I'm reading about the Halting problem. $H(\langle M,w\rangle)$ is a machine which will solve the Halting problem, and then using machine $H$ one creates a new machine $D$ and we run $H$ on ...
1
vote
1answer
86 views

What is the complexity of timing a turing machine? [duplicate]

I can't find the standard name for this problem, so lets call it TIMING, it takes as input a Turing machine $F$ with its input $i$, and a number of steps $n$. It returns yes if $F(i)$ halts in less ...
3
votes
1answer
372 views

Computer Security versions of the Halting Problem

I'm plenty familiar with the Halting Problem for Turing Machines. It occurred to me after reading several posts on this site that it would be interesting, educational and useful to start a list of ...
1
vote
1answer
113 views

Why would total comparison of functions solve the Halting problem?

Why would total comparison of procedures solve the Halting problem? I've read that if all procedures could be represented syntactical e.g. in Scheme, then they could be compared structurally using ...
1
vote
1answer
772 views

Example of a language that is neither recognizable nor co-recognizable?

Is there an example of a language that is neither recognizable nor co-recognizable? A relevant (easy) theorem is that a language is decidable iff it is recognizable and co-recognizable. An example ...
2
votes
1answer
401 views

decidability of artificial intelligence

Not sure whether this is the correct place to post the question. some of my terms might not accurate. currently AI is used for classification, inference, and so forth, is AI problem decidable? for ...
1
vote
2answers
594 views

What is the amount of programs for which we can solve the halting problem?

The halting problem is undecidable of course. This implies that there is at least one program for which we cannot decide whether it halts or not, because theoretically, if all we know is that the ...
1
vote
1answer
49 views

How big is the class of problems that can be analysed to halt with static analysis. Is this class sufficient for any practical purposes? [closed]

When the halting problem is discussed, often the counterproof consists of some unsolved mathematical problem or a self-reference. Is the halting problem decidable for pure programs on an ideal ...
24
votes
4answers
4k views

Is the halting problem decidable for pure programs on an ideal computer?

It's fairly simple to understand why the halting problem is undecidable for impure programs (i.e., ones that have I/O and/or states dependent on the machine-global state); but intuitively, it seems ...
3
votes
0answers
176 views

Are Turing machines with a limited but exponential tape decidable?

The Halting problem for Turing machines which work on a tape of at most $k$ cells can be solved: There is a limited number of distinct configurations available, providing an upper bound of steps ...
0
votes
0answers
110 views

Halting problem and simulation of intelligence [duplicate]

According to halting problem, there is no algorithm which can decide if another algorithm and its input will halt or not. Suppose human intelligence can be simulated in a computer. Also suppose than ...
3
votes
4answers
269 views

If modern computers aren't actually Turing-complete, does that mean that it is possible to determine if a program run on such a computer halts?

The halting problem says that it is impossible to create a general algorithm which can for all inputs and programs determine whether they halt. However, this assumes that the programs and/or the ...
2
votes
3answers
189 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 ...
6
votes
1answer
570 views

Machine Learning to predict the Halting Problem

I seem to recall an academic paper from some years ago which used machine learning (possibly genetic or evolutionary programming) to predict whether a Turing Machine would halt. By predict, I mean ...
10
votes
4answers
3k views

Can a Turing Machine (TM) decide whether the halting problem applies to all TMs?

On this site there are many variants on the question whether TMs can decide the halting problem, whether for all other TMs or certain subsets. This question is somewhat different. It asks whether ...
6
votes
1answer
2k views

Decidability of halting problem for DPDAs with $\epsilon$-transitions?

For LBAs it's rather easy to prove the decidability of the halting problem, as there can only be a finite number of different configurations when using limited space. But what about PDAs with $\...
0
votes
1answer
61 views

When reducing from HALT, can you create a Turing machine that asks whether a simulation stops?

Lets say I am doing a reduction from $\mathrm{HALT}_{\mathrm{TM}}$ to another language $S$, in order to prove that $S$ is not decidable. For this I need to build a new Turing machine, $M'$. Can I ...
4
votes
2answers
92 views

Resource bounded reductions for RE-Complete problems

Given that the halting problem is RE-Complete, we can reduce any problem in RE to an instance of the halting problem. Are there are any results on the time-bounds for this reduction? Can we do this ...
1
vote
2answers
566 views

Does the the undecidability of the Halting Problem eliminate the possibility of 'Hard AI'? [duplicate]

I'm defining 'Hard AI' as a human-equivalent intelligent machine, or beyond that. Contrast with 'Soft AI' the type of software that runs on your email filter for example. I've been chewing on this ...
2
votes
2answers
117 views

Does the Halting Problem have practical relevance? I can calculate all outputs for a finite number of states and inputs [duplicate]

Coming from a digital functional hardware verification background, I don’t really understand the Halting Problem. I can represent the program as a state machine and show whether all inputs in all ...
4
votes
1answer
1k 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
58 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 $\...
2
votes
1answer
65 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
812 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
66 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 ...
5
votes
1answer
650 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 $\...
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 ...
7
votes
3answers
897 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 ...
3
votes
2answers
3k 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 ...