Questions tagged [halting-problem]

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

36 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
0answers
180 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 ...
4
votes
0answers
92 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 ...
3
votes
0answers
204 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 ...
1
vote
0answers
34 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
1answer
43 views

the problems that could exist if halting problem is solved

What problems might exist if halting problem is solved. If there exist an oracle that can compute whether a given machine halts or not then what would be problems that could exists if such oracle is ...
1
vote
0answers
33 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 ...
1
vote
0answers
27 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 ...
1
vote
0answers
42 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?
1
vote
0answers
41 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
0answers
68 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 ...
1
vote
0answers
18 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
vote
0answers
258 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)$ ...
1
vote
0answers
59 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 $\...
1
vote
0answers
23 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
0answers
89 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 ...
0
votes
0answers
30 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 ...
0
votes
0answers
24 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 ...
0
votes
0answers
36 views

A Turing machine for which it is impossible to predict whether it halts or not on a fixed input

The halting problem is undecidable, i.e. $\not \exists$ $M$ Turing machine s.t. for every $(M_0,w_0)$ input where $M$ is the description of a Turing machine and $w_0$ is an input word, the output of $...
0
votes
1answer
36 views

On the computable function of a problem that halts

Let's say program $P$ with given input $i$ is found to halt (or doesn’t halt) by a Turing machine. Is it true that the same program $P$ with input $F(i)$ also halts (or not, respectively), where $F$ ...
0
votes
0answers
60 views

What Makes A TM undecidable (using Recursion Theorem)

PROOF :We assume that Turing machine H decides ATM for the purpose of obtaining a contradiction. We construct the following machine B. B =“On input w: Obtain, via the recursion theorem, ...
0
votes
0answers
16 views

Given we restrict the time and memory allowed what bounds can we place on a halting decider?

If a program is given as much memory and as much time to execute as it wants, then the halting problem is undecidable, and by Rice's theroem all non-trivial, semantic properties of programs like that ...
0
votes
0answers
30 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?
0
votes
2answers
115 views

Can we enumerate finite sequences which have no halting continuation?

Note: this question has been cross-posted to Math.SE, after about a week here. I am trying to deepen my understanding of the relationship between the Halting Problem and Godel's Completeness Theorem (...
0
votes
1answer
103 views

Define the following problem as a language and prove that it is undecidable with a reduction from the halting problem.

...Knowing whether a Turing machine will ever output your name on the tape. The language is the set of all TMs that print your name. Reduce from HALT TM. I had this problem on my exam. From my ...
0
votes
0answers
54 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 ...
0
votes
0answers
143 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.....
0
votes
0answers
78 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 ...
0
votes
0answers
39 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 ...
0
votes
0answers
275 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 ...
0
votes
0answers
113 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" ...
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 ...
0
votes
0answers
68 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 ...
0
votes
0answers
643 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&...
0
votes
0answers
169 views

Does the head of TM M ever move into cell x when processing Input I?

The question is whether this is recursive or not. I first thought that it wasn't but then I read this question which seems similar and is recursive. Is it decidable whether a TM reaches some position ...
-1
votes
1answer
43 views

Are non halting programs not computable?

Are non halting programs not computable? How are these two sets of programs related: is a non halting program just a specific example of a type of program that is not computable or is it technically ...
-1
votes
1answer
65 views

Does solving all Halting problem instances 'in the limit' imply we solve an undecidable problem?

The recent Arxiv paper "Learning the undecidable from networked systems" attempts to construct a network of $N$ Turing machines$^1$ that can solve the Halting problem for any program of size $O(\log N)...