"Turing Machines & Undecidability" — Practice

Question 1

Which problem is decidable?

Accepted Answer

B

Question 2

A language L is recursively enumerable and its complement is also recursively enumerable. What follows?

Accepted Answer

B

Question 3

A nondeterministic Turing machine is compared with a deterministic one. Which statement is correct?

Accepted Answer

B

Question 4

Prove that the problem of deciding whether a Turing machine accepts at least one string is undecidable.

Accepted Answer

This is the non-emptiness problem. Prove it undecidable by reduction from halting.

Assume a decider N exists that, given an encoded machine, always halts and reports whether its language is non-empty.

Take an arbitrary instance of the halting problem: a machine M and an input w.

Construct a new machine P as follows. On any input x, P ignores x entirely, writes w on its tape, and simulates M on w. If that simulation halts, P accepts.

Now determine P's language in each case.

If M halts on w, the simulation inside P terminates for every input x, so P accepts every string. Its language is all strings, which is certainly non-empty.

If M does not halt on w, the simulation never terminates, so P never reaches its accepting step for any input. Its language is empty.

Therefore P has a non-empty language exactly when M halts on w.

Running N on P would answer the halting question for M and w, and since N always halts by assumption, this would decide the halting problem.

The halting problem is undecidable, so N cannot exist and non-emptiness is undecidable.

Note that Rice's theorem gives the same conclusion in two lines: non-emptiness is a property of the language, and it is non-trivial since some machines accept nothing and others accept everything. The explicit reduction is worth being able to write because questions sometimes ask for it directly.

Question 5

For each property, state whether Rice's theorem applies and why: the machine has more than 100 transitions; the language contains the string ab; the machine halts within 20 steps on the empty input.

Accepted Answer

Rice's theorem requires two conditions: the property must be about the language recognised, and it must be non-trivial.

Property one: more than 100 transitions. This is a property of the machine's description, not its language. Two machines recognising the identical language can have wildly different transition counts, so the property fails the first condition. Rice does not apply, and the property is decidable by counting transitions in the encoding.

Property two: the language contains the string ab. This is purely about the set of accepted strings, so it is a language property. It is non-trivial, since some recursively enumerable languages contain ab and some do not. Both conditions hold, so Rice applies and the property is undecidable.

Property three: halts within 20 steps on the empty input. This concerns the machine's behaviour rather than the description, but it is not a property of the language. Two machines with the same language can differ in how fast they accept, so it fails the first condition. Rice does not apply.

Moreover it is decidable directly: simulate for exactly 20 steps and report whether the machine halted. The simulation always terminates because the step count is bounded.

The general lesson is that Rice's theorem is powerful but narrow. It settles language properties instantly and says nothing about syntactic properties or bounded-resource questions, both of which are routinely decidable.

Question 6

Prove that recursive languages are closed under complement, and explain why the same argument fails for recursively enumerable languages.

Accepted Answer

Let L be recursive, so there is a Turing machine M that halts on every input and correctly accepts members of L and rejects non-members.

Construct a machine M-prime that runs M on its input and then inverts the verdict: accept where M rejected, reject where M accepted.

M-prime always halts, because M always halts and inverting a verdict takes no additional steps. It accepts exactly the strings M rejected, which is exactly the complement of L.

So the complement is recursive, and the class is closed under complement.

The argument fails for recursively enumerable languages at a single point: the semi-decider for L is not guaranteed to halt on non-members. On a string outside L, it may run forever, and there is no moment at which the construction could invert a verdict, because no verdict is ever produced.

Inverting only the halting behaviour does not help either. A machine that accepts when the original loops is not implementable, since detecting that another machine will loop forever is precisely the undecidable halting question.

The formal consequence follows from the parallel-simulation theorem. If the class were closed under complement, then for every recursively enumerable L both L and its complement would be semi-decidable, making L decidable. That would collapse the recursively enumerable and recursive classes, which the halting language contradicts.

The underlying asymmetry is between confirmable and unconfirmable facts: acceptance can be witnessed by a finite computation, whereas non-acceptance cannot.

Question 7

Prove the halting problem undecidable, and identify precisely which assumption the proof depends on.

Accepted Answer

Assume for contradiction that a machine H decides halting. On input consisting of an encoded machine M and a string w, H always halts, answering yes if M halts on w and no otherwise.

Using H, construct a machine D that takes a single input x, interpreted as an encoded machine.

D runs H on the pair consisting of x and x itself — that is, it asks whether the machine x halts when given its own encoding.

If H answers yes, D deliberately enters an infinite loop.
If H answers no, D halts immediately.

D is constructible, since H is assumed to exist and always halt, and both looping and halting are trivially implementable.

Now run D on its own encoding and consider the two possibilities.

Suppose D halts on input D. Then by the definition of H, the call H(D, D) answered yes. But D was built to loop forever whenever H answers yes, so D does not halt. Contradiction.

Suppose D does not halt on input D. Then H(D, D) answered no. But D was built to halt immediately whenever H answers no, so D halts. Contradiction.

Both possibilities are impossible, so the assumption that H exists is false and halting is undecidable.

As to the assumption the proof depends on: the only one used is that a machine can be encoded as a string and supplied to another machine as input, including to itself.

Nothing about tapes, transitions, alphabets or state counts entered anywhere. That is why the result is not an artefact of the Turing model, and why an equivalent limitation appears in every computational framework rich enough to encode its own programs.

Question 8

Classify these as recursive, recursively enumerable but not recursive, or not recursively enumerable: the halting language; its complement; the set of machines halting on all inputs; the set of machines with exactly 5 states.

Accepted Answer

The halting language is recursively enumerable but not recursive.

Semi-decidable: a universal machine simulates the encoded machine on the given input and accepts if the simulation ever halts. Members are always eventually accepted.

Not recursive: the diagonalisation argument. A decider could be turned against itself to produce a machine that halts exactly when it does not.

The complement of the halting language is not recursively enumerable.

If it were, then both it and the halting language would be semi-decidable, and by parallel simulation the halting language would be decidable, contradicting the previous result. Intuitively, halting can be confirmed by observing it, whereas non-halting cannot be confirmed by any finite observation.

The set of machines halting on all inputs — the totality problem — is not recursively enumerable either.

Semi-deciding it would require confirming halting on infinitely many inputs, and no finite computation can do so. Even after simulating a million inputs successfully, the next might loop. It is strictly harder than halting.

The set of machines with exactly 5 states is recursive.

This is a syntactic property of the encoding. Parse the description, count the states, and answer. The procedure always terminates and always gives the correct verdict, so the language is decidable.

The pattern worth extracting: syntactic properties are recursive; properties confirmable by a finite witness are recursively enumerable; properties requiring confirmation of a universal statement over infinitely many cases usually fall outside even that.

Question 9

Explain why reducing problem A to problem B proves B hard when A is hard, but proves nothing when the reduction runs the other way.

Accepted Answer

A reduction from A to B is a computable function f that converts any instance x of A into an instance f(x) of B such that x is a yes-instance of A exactly when f(x) is a yes-instance of B.

The key consequence is that a decider for B yields a decider for A. Given an instance x of A, compute f(x), run the B-decider on it, and return the answer. Since f is computable and the B-decider always halts, the composite always halts and is correct.

Now take the contrapositive. If A has no decider, then B can have none either, because a B-decider would have produced an A-decider. So a reduction from a known-undecidable A to a new problem B proves B undecidable.

The reverse direction proves nothing about difficulty. Suppose instead we reduce B to A, converting instances of the new problem into instances of halting. That shows a halting-decider would solve B. But no halting-decider exists, so the implication has a false antecedent and yields no information about B whatever.

An analogy makes the asymmetry clear. Showing that a new problem can be solved using an oracle for an impossible problem tells you nothing, because the oracle is unavailable. Showing that an impossible problem can be solved using an oracle for the new problem tells you the new problem's oracle must also be unavailable.

The practical rule for constructing such proofs is therefore fixed. Start with an arbitrary instance of the known-hard problem, build from it an instance of the new problem, and show the answers coincide. The construction always runs in that direction, and the machine being built is always the one fed to the hypothetical new decider.

Practice — "Turing Machines & Undecidability"

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities