Questions tagged [halting-problem]

Given a program and the input for it, does it halt or run forever?

3 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
10
votes
0answers
200 views

The halting problem in computational models weaker than Turing machines

What are the main results and/or literature on the (self) halting problem for other machines than Turing machines? Alternatively, what would be the right keywords or tags to search for it. I am ...
2
votes
0answers
68 views

Is there value in a faster soultion for the Halting Problem in a Linear Bounded Automata?

Sorry for being so informal, but I was thinking a bit about how the Halting Problem is solvable on a LBA but very very slow, in that if you have gone though more states in execution then the total ...
0
votes
0answers
59 views

Turing meta-oracle

Let H(P) be some program that given P('s source code) computes whether or not P terminates, i.e. solves the halting problem. H only needs to terminate if P terminates. (This disallows solutions like ...