Question

a.    Briefly but clearly describe any valid method to prove that decision problem X is decidable.

b. Briefly but clearly describe any valid method to prove that decision problem X is acceptable/recognizable.

c. Briefly but clearly describe any valid method to prove that decision problem X is undecidable.

d. . Briefly but clearly describe any valid method to prove that decision problem X is not Turing-acceptable.

Answer 1

a) By definition, a language is decidable if there exists a Turing machine that accepts it, that is, halts on all inputs, and answers "Yes" on words in the language, "No" on words not in the language. Therefore one way of showing that a language is decidable is by describing a Turing machine that accepts it.

b) Turing-decidable language
Answer: A language A that is decided by a Turing machine; i.e., there is a Turing machine
M such that M halts and accepts on any input w ∈ A, and M halts and rejects on input
input w not ∈ A; i.e., looping cannot happen.
Turing-recognizable language
Answer: A language A that is recognized by a Turing machine; i.e., there is a Turing
machine M such that M halts and accepts on any input w ∈ A, and M rejects or loops on
any input w not ∈ A.

c)

Undecidability

Definition: A decision problem is a problem that requires a yes or no answer.

Definition: A decision problem that admits no algorithmic solution is said to be undecidable.

• No undecidable problem can ever be solved by a computer or computer program of any kind. In particular, there is no Turing machine to solve an undecidable problem.

  We have not said that undecidable means we don't know of a solution today but might find one tomorrow. It means we can never find an algorithm for the problem.

• It is not obvious how to show no solution can exist.We can do so by constructing a logical paradox.nce we've seen one problem that is undecidable, it is often easy to show that other similar problems must also be undecidable.

The Halting Problem is Undecidable: Proof

Proof by contradiction: Assume we have a procedure HALTS that takes as input a program P and input data D and answers yes if P halts on input D and no otherwise.

• Of course we can't just have HALTS simulate P on input D, since if P doesn't halt, we'll never know exactly when to quit the simulation and answer no.

Since there are no assumptions about the type of inputs we expect, the input D to a program P could itself be a program.

• Compilers and editors both take programs as inputs.
• Given a Pascal compiler written in Pascal, we might want to know if the compiler halts when given itself as input.

Given the program HALTS, we can construct a new (more limited) program that tests whether a program P halts when the input data is a copy of P.

      procedure NEWHALTS(P);
        if HALTS(P,P) then writeln('Yes');
        else writeln('No');
      

Proof Continued

Given NEWHALTS, we can construct another program that does just the opposite of NEWHALTS:

      procedure OPP(P);
        if NEWHALTS(P) outputs 'Yes' then
            loop forever
        else halt;
      

What happens when we call OPP(OPP)?

• Inside OPP, we call NEWHALTS(OPP), which calls HALTS(OPP,OPP). If OPP halts when fed OPP as input then the call OPP(OPP)loops forever.
• If OPP doesn't halt when fed OPP as input, then the call OPP(OPP) halts.
• OPP(OPP) can neither halt nor loop forever.

This is a contradiction! Since our only assumption was the existence of HALTS, procedure HALTS cannot exist

D) .Given a program P and a language L, we say P accepts L, if L = L(P). A language L is Turing
acceptable if there exists a program P such that P accepts L, i.e., L = L(P). A language L is
Turing decidable if there exists a program that accepts L, and P always halts.
If L is Turing acceptable, then there exists a program P such that: for any string x, if x ∈ L,
then P accepts x. If x /∈ L, then there are two possibilities: 1)P may halt and does not output
“ACCEPT”, or 2)P may run forever.
If L is Turing decidable, then there exists a program P such that: for any string x, if x ∈ L,
then P accepts x, else P rejects x.