1
$\begingroup$

Is it possible for a Turing machine to halt without reading the complete input string. Suppose there is a string "adc" preceded and succeeded by infinite number of blanks. Can a Turing machine halt after reading just "a" and never touching "dc" or any of the blanks. If yes, will this string be accepted or rejected?

$\endgroup$
2
$\begingroup$

Nothing special happens if the Turing machine doesn't read the entire input. For example, the machine can halt immediately, without looking at the input at all. If the Turing machine halts at an accepting state, then the input is accepted. If it halts at a rejecting state, then the input is rejected. In this way you can construct a Turing machine that accepts all inputs or that rejects all inputs, in both cases without looking at the input string at all.

In your example, the machine accepts "adc" iff it accepts "a".

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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