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
5
votes
0
answers
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 ...
- 79
4
votes
0
answers
391
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
3
votes
0
answers
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
3
votes
0
answers
304
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
2
votes
0
answers
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
2
votes
0
answers
334
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
0
answers
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 ...
- 345
1
vote
0
answers
88
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
0
answers
156
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 ...
- 201
1
vote
0
answers
42
views
How to reduce $\overline{K} \leq L$, or how to show semi-decidability of a given language?
I'm currently preparing for an exam and I'm having trouble to solve the following Questions.
Let $w \in \{0,1\}^*$ and let $L$ be a language defined as follows
$$L = \{w \mid \mathsf{time}_{M_w}(x) \...
- 321
1
vote
0
answers
103
views
If a turing machine can't solve the halting problem for a machine X, does this imply that X is at least as powerful as a turing machine?
Say I have a deterministic machine X, and I prove that a turing machine can't solve the halting problem for this machine when given a certain input. Does this imply that this machine X is turing-...
1
vote
0
answers
83
views
Is Halting problem only applicable to infinite languages
Is the halting problem, only applicable for infinite languages?
I assume that if the language is finite, then we can search over all words?
- 511
1
vote
0
answers
38
views
How to create model for a powerful language whose programs are guaranteed to terminate?
I'm creating a powerful regular expression matching system that can be augmented by adding small microprograms to deterministic finite automaton (DFA) states. The microprogram solves the big bang ...
- 283
1
vote
0
answers
28
views
Is there an impossibility to mechanically distinguish between sets and classes?
Assuming only computable functions, and in line with set theory, defining a "proper class" as a collection that is itself not allowed to be a member of a set. A "collection" is then defined as either ...
- 51
1
vote
0
answers
53
views
Computational models where halting problem is solvable
Are there computational models that can be considered useful for solving common programming problems, where it can be proven that computation will terminate for all possible inputs?
- 153
1
vote
0
answers
42
views
What portion of all possible turing machines halt?
Has anyone estimated Chaitin's constant for Turing machines with an empty tape as input?
1
vote
0
answers
80
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 ...
- 488
1
vote
0
answers
24
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 ...
- 1,199
1
vote
0
answers
62
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 $\...
- 742
1
vote
0
answers
30
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 ...
- 123
1
vote
0
answers
101
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 ...
- 143
0
votes
1
answer
81
views
Mapping Reduction from HALT?
I've been given a task to determine whether L={〈M〉|M is a TM that loops on the input c (a constant)} is decidable. I can prove co-L is recognizable so I figured a reduction from HALT to co-L would ...
- 1
0
votes
0
answers
42
views
How do people working on the Busy Beaver function keep track of all the turing machines?
I'm a CS undergrad so forgive me if this question isn't formulated well. I got curious about the Busy Beaver function recently, and it got me wondering how all the n-state Turing machines are kept ...
- 101
0
votes
0
answers
25
views
Effectively universal Turing machines and Turing-completeness?
An effectively universal Turing machine $T$ is a Turing machine for which there exists a recursive reduction $f$ such that $\forall A:U(A)=T(f(A))$, where $A, f(A)$ are finite sequences of symbols (...
- 1,632
0
votes
1
answer
68
views
A program that solves the Halting Problem for programs with N states
My question relates to the conclusions drawn from the Halting Problem. I understand that the Halting Problem proves that no program H(P,i) exists that determines if P(i) halts or not for P in general. ...
0
votes
0
answers
24
views
Reduce A ∶= {x ∈ N ∣ x < 10} to Halting Problem on empty tape
I am preparing for an exam in computability and still learning about the idea of reductions. I found an interesting problem to start with and am curious if my approach is correct:
Let H0 be the ...
- 1
0
votes
3
answers
101
views
Does exist an algorithm that decides whether a program halts or not as its timeout approaches to infinity?
By an algorithm $A(p, t)$ attempting to decide whether the program $p$ halts or not by running the program for $t$ seconds (the timeout) and trying to prove that it doesn't halt at the same time, can ...
- 51
0
votes
1
answer
51
views
Reduction from a language with unknown decidability to HALT
We were taught to use reductions in order to show that a given L is undecidable. My question is, given some definition of a new L, is there a way to find a reduction
$$
L\leq_mHALT
$$
So that I can ...
- 1
0
votes
0
answers
64
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 ...
- 101
0
votes
0
answers
65
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
0
votes
0
answers
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
0
votes
0
answers
121
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
0
votes
0
answers
65
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 ...
- 3
0
votes
0
answers
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
0
votes
0
answers
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
0
votes
0
answers
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 ...
- 1
0
votes
0
answers
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 ...
- 135
0
votes
0
answers
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
0
votes
0
answers
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
0
votes
0
answers
169
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
0
votes
0
answers
105
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 ...
- 135
0
votes
0
answers
205
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
0
votes
0
answers
272
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
0
votes
0
answers
217
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
0
votes
0
answers
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
0
votes
0
answers
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
0
votes
0
answers
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 ...
user81528
0
votes
0
answers
139
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
0
votes
0
answers
32
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,199
0
votes
0
answers
906
views
Reducing the halting problem to the uniform halting problem
As stated here https://books.google.cz/books?id=dwpeNRgjK68C&pg=PA57&lpg=PA57&dq=uniform+halting+problem&source=bl&ots=qsbv_672W9&sig=NDcebhxrwcYdF-P15dor565l8Jc&hl=en&...
