# Questions tagged [halting-problem]

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

56 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
205 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 ...
405 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 ...
• 1,710
192 views

### Does this paper by Patrick Cousot describe an undecidable method for model checking?

All of the discussion is in the context of this paper. I think that the whole procedure that the paper describes is not decidable, because if we can have an algorithm for it, then we can solve halting ...
• 31
307 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 ...
• 339
64 views

### An approximation variant of the halting problem

It always has been bugging me that we (humans) know pretty easily when most programs we write halt or not, but the halting problem is still undecidable. I have just thought of a variant approximation-...
• 11.6k
337 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)$ ...
• 135
1 vote
35 views

### How much is decidability compromised within this restriction of the fixpoint combinator?

Though purely functional programming languages, such as Haskell, is commonly thought to have no side-effects, there is a caveat: Recursive calls may hang. I considered this to be undesirable, and ...
• 367
1 vote
90 views

### Understanding unprovable halting, model theory, and (in)completeness

I know computability, but not model theory and logic, so this question may be naive or confused in that respect. A blog post of Scott Aaronson mentions a Turing Machine $M^*$ such that the statement P:...
• 4,129
1 vote
170 views

### Why do PDAs always halt?

Can’t a PDA get stuck in a cycle of blank transitions? Should the implementation detect such cycles and do something about them? That seems quite complex to consider all the edge cases. Does the ...
• 211
1 vote
44 views

• 1
76 views

### Is game of life an example to halting problem?

I am working on a solution that can say if an initial composition is going to live forever or eventually die without calculating each generation until it reaches a stable or an ever-repeating cycle in ...
66 views

### Reduction from Diophantine Equation Problem to Halting Problem

I want to study the reduction from the Diophantine Equation Problem (Hilbert's tenth problem) to the Halting problem. Can you either explain it to me or give me a credible source from which I can ...
• 1
56 views

### Is there a good example of computing a sequence that illustrates the Halting Problem?

I know that Busy Beaver problem can be used to illustrate the Halting Problem and it's probably the canonical problem used when talking about the Halting Problme . But long time ago I came across some ...
• 101
123 views

### proof that halting problem is undecidable

In the book Formal languages and automata by Peter Linz, 4th edition (Jones & Bartlett Learning), on pages 300-301, there is a proof for the fact that the halting problem is undecidable. The proof ...
• 89
70 views

### How should I imagine $M_w[\epsilon]\downarrow$ for the empty halting problem or $M_w[w]\downarrow$

I'm learning about computability problems e.g. reducing the general halting problem to the halting problem on a blank tape. But before I can understand this problem I first have to understand what ...
36 views

### Is this version of the halting problem NONELEMENTARY?

Input: A TM $M$ and an integer $k$. Output: Yes if $M$ halts within $2\uparrow\uparrow k$ steps (where $\uparrow\uparrow$ is tetration (iterated exponentiation)). Intuitively, it seems like this has ...
• 1
61 views

### halting problem vs watchdog

I have a theory that all finite state machines can be monitored by a second turing machine with infinite tape to determine if the state of the first machine was repeated thus reaching the conclusion ...
• 101
20 views

### Other than correlation of events, what is the halting problem about?

Object B can be in two state 1(stopped), and 2(running) at an arbitrary time t in the future. Object A can be in two states x, and y at t0. However, if A is in state x, B must be in state 2 at t, and ...
46 views

### Can you write an algorithm that can generalize another algorithm?

Can you write an algorithm which can take in a given function/algorithm, and produce a distribution of generalizations of the function at hand? One such simple example of generalization might mean the ...
27 views

### Computability of a halting oracle for a specific class of machines

Let us consider the set of machines/algorithms with constant inputs (I would have preferred to say no inputs but I was told that every algorithm/machine has to have an input). We call $\mathcal{M}$ ...
• 185
59 views

### Why is it impossible to iterate over all TMs with $n$ states and $k$ symbols that halt after $m$ steps on $\epsilon$?

Define $\{\sigma(n,k,m,i)\}_{i=1}^{l_m}$ an ordered set of all TMs with $n$ states and $k$ symbols that halt after $m$ steps on $\epsilon$ There are $(2kn)^{kn}$ TMs with $n$ states and $k$ symbols, ...
• 317
170 views

### Can a pushdown automaton solve the halting problem for another Pushdown automaton?

Can a pushdown automaton solve the halting problem for another Pushdown automaton? It's already shown here turing machine can solve the halting problem for a pushdown automaton. Decidability of ...
• 356
108 views

### Is the undecidability of a given problem undecidable?

Given an input problem P, can you construct an algorithm A to compute whether or not P is decidable or undecidable? In other words, is the undecidabiliy of a problem undecidable? My initial guess is ...
207 views

### Can a halting configurations of a Turing Machine has the same state of another configuration has?

At first, I believed since the state a halting configuration is at will be a halting state, whenever a configuration goes into that state, the TM halts. Hence, there should not exist two ...
• 11
273 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 ...
• 23
218 views

### how to prove that the diagonal language K is r.e

To prove that K= $\{x \mid \phi_x(x)$ halts and accepts$\}$ is r.e.: we can recognize K by: for any x, we simply run x on machine $\phi_x$ and accept if the machine accpets else reject and that's it.....
• 139
89 views

### How to properly reduce a set of TMs to the halting problem?

Consider a standard enumeration of Turing machines ($T_0, T_1, T_2$, ...). Then, let language A be defined as $A = \{n \in\mathbb N | T_n(\lambda) \downarrow\}$. I need to reduce it to the halting ...
• 33
45 views

### Can machines of finite size ever solve their own halting problems?

A real-life computer can only store programs and inputs up to a certain length, which means that its halting problem can be solved with a lookup table. The most obvious way to represent this table ...
• 385
390 views

### Need Help Understanding Proof by Contradiction for Halting Problem

I understand what the halting problem describes, but I do not understand how the proof by contradiction associated with it proves that it is impossible to solve. The proof by contradiction can be ...
140 views

### Can there be an oracle that solves its own halting problem?

Since the same contradiction from the Turing machine is still there, we allow the oracle not always return an exact value, and say it solves the halting problem if the probability of returning "HALT" ...
• 249