Theory of Computation: Question Set – 26

What is the difference between a decidable and a semi-decidable language?

A decidable language is a language for which there exists an algorithm that can determine whether a given string belongs to the language or not. A semi-decidable language is a language for which there exists a Turing machine that can accept all strings that belong to the language, but may not halt on strings that do not belong to the language.

Can a semi-decidable language be undecidable?

Yes, a semi-decidable language can be undecidable. For example, the language of all Turing machines that halt on empty input is semi-decidable but not decidable. This is because we can construct a Turing machine that accepts all machines that halt on empty input, but there is no algorithm that can determine whether a given machine halts on empty input or not.

Can a language be both decidable and semi-decidable?

Yes, a language can be both decidable and semi-decidable. For example, the language of all binary strings that represent a valid Turing machine is both decidable and semi-decidable. We can construct a decider that checks whether the input is a valid binary string representing a Turing machine, and we can construct a Turing machine that simulates the given Turing machine on the empty input and accepts if the simulation halts.

Is the set of all undecidable languages countable or uncountable?

The set of all undecidable languages is uncountable. This is because there are only countably many Turing machines, but there are uncountably many languages over any non-trivial alphabet. Therefore, there must be uncountably many languages that are undecidable.

Can we prove that a language is undecidable?

Yes, we can prove that a language is undecidable by showing that there is no algorithm that can decide whether a given string belongs to the language or not. This can be done using techniques such as diagonalization, reduction, or the use of other undecidable problems.

What is Rice’s theorem?

Rice’s theorem states that any non-trivial property of the behavior of a Turing machine is undecidable. More specifically, if a language depends on any non-trivial aspect of a Turing machine’s behavior (such as the number of states, the number of transitions, or the language it recognizes), then that language is undecidable.

Can a language be decidable if its complement is undecidable?

Yes, it is possible for a language to be decidable if its complement is undecidable. For example, the language of all binary strings that represent a valid Turing machine is decidable, even though its complement (the language of all binary strings that do not represent a valid Turing machine) is undecidable.

What is the difference between a reduction and a mapping reduction?

A reduction is a method for showing that one problem is at least as hard as another problem. A mapping reduction is a specific type of reduction that maps instances of one problem to instances of another problem in a way that preserves the answer. More formally, a mapping reduction from problem A to problem B is an algorithm that transforms instances of A into instances of B in polynomial time, such that the answer to the transformed instance of B is the same as the answer to the original instance of A.