Skip to main content

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
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 ...
user12262's user avatar
4 votes
0 answers
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 ...
Ben I.'s user avatar
  • 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 ...
Senmorta's user avatar
3 votes
0 answers
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 ...
mafu's user avatar
  • 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-...
nir shahar's user avatar
  • 11.6k
2 votes
0 answers
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)$ ...
MoreOver's user avatar
  • 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 ...
Dannyu NDos's user avatar
1 vote
0 answers
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:...
usul's user avatar
  • 4,129
1 vote
0 answers
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 ...
HappyFace's user avatar
  • 211
1 vote
0 answers
44 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) \...
Algebruh's user avatar
  • 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-...
Andrew Rashenda's user avatar
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?
WeCanBeFriends's user avatar
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 ...
juhist's user avatar
  • 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 ...
erik's user avatar
  • 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?
zduny's user avatar
  • 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?
Alecto Irene Perez's user avatar
1 vote
0 answers
81 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 ...
User Not Found's user avatar
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 ...
hawkeye's user avatar
  • 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 $\...
Don Fanucci's user avatar
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 ...
McAngus's user avatar
  • 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 ...
Henry akpo's user avatar
0 votes
1 answer
113 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 ...
Diode's user avatar
  • 1
0 votes
0 answers
44 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 ...
Slim Shady's user avatar
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 (...
rus9384's user avatar
  • 1,684
0 votes
1 answer
70 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. ...
Vincenzo Buselli's user avatar
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 ...
dport's user avatar
  • 1
0 votes
3 answers
117 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 ...
sbh's user avatar
  • 51
0 votes
1 answer
53 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 ...
John's user avatar
  • 1
0 votes
0 answers
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 ...
Yağız Alp Ersoy's user avatar
0 votes
0 answers
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 ...
Mgh's user avatar
  • 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 ...
RubenLaguna's user avatar
0 votes
0 answers
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 ...
Ronald's user avatar
  • 89
0 votes
0 answers
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 ...
linuxxx's user avatar
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 ...
N O's user avatar
  • 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 ...
acacia's user avatar
  • 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 ...
frt132's user avatar
  • 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 ...
ZeroMaxinumXZ's user avatar
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}$ ...
C Marius's user avatar
  • 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, ...
user10364768's user avatar
0 votes
0 answers
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 ...
blademan9999's user avatar
0 votes
0 answers
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 ...
ZeroMaxinumXZ's user avatar
0 votes
0 answers
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 ...
MayRain's user avatar
  • 11
0 votes
0 answers
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 ...
pjs's user avatar
  • 23
0 votes
0 answers
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.....
user352102's user avatar
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 ...
WOW's user avatar
  • 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 ...
Display Name's user avatar
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 ...
user avatar
0 votes
0 answers
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" ...
l4m2's user avatar
  • 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 ...
hawkeye's user avatar
  • 1,199
0 votes
0 answers
911 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&...
Daniel Stodůlka's user avatar