1
$\begingroup$

Assume we have an oracle that tells, given a linear bounded automaton, if there exists an input on which it halts.

Can we then solve the real halting problem (i.e. decide if a given Turing machine halts on a given input)?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

I would imagine yes. The emptiness problem for context-sensitive grammars is undecidable, presumably by a reduction from the halting problem. Given the equivalence between LBA and context-sensitive grammars, this implies that the same should hold for your problem too. I suggest you verify that this is correct by working through the proofs of these statements, to check that they indeed give an explicit reduction from the halting problem; assuming they do, you will have the answer to your question.

Improve this answer
$\endgroup$
1
$\begingroup$

Yes, we can do that. The basic idea is that from an arbitrary Turing machine $M$ we can produce an LBA $C$ which checks whether its input codes a valid sequence of configurations for $M$ starting with the starting state and the empty tape, and ending in a halting state. Now we have that $C$ will accept some input if and only if $M$ halts on the empty input.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.