HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Does a non deterministic Turing machine which is a decider halt on all branches for all inputs?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
inputsbranchesnondeciderwhichalldeterministicdoesmachineturing

Problem

Does a non deterministic Turing machine which is a decider halt on all branches for all inputs??

I know it must halt on all branches for a string not in language, but for a string in language, NDTM requires only one accepting branch so even if some other branch is infinite, NDTM will still accept the string

Solution

You can define it either way. The simple way to define it is to say that every branch must halt for every input. Alternatively, you can say that, if the input is in the language, at least one branch must accept, so you don't care if the others reject or just fail to halt; if the input is not in the language, then every branch must reject.

Both in terms of computability and complexity, you can show that the two definitions are completely equivalent.

Context

StackExchange Computer Science Q#54486, answer score: 4

Revisions (0)

No revisions yet.