4.1 Undecidability

Divide TM into two catagories:

  • TMs that halts whether or not it accepts its input
  • TMs that may run forever on inputs they don't accept

So we have to show some problems to be undecidable.

i.e. Does this TM accept this input?

Recursive & Recursively Enumerable

A language L is recursive if L=L(M) for some Turing machine M such that:

  • If w is in L, then M accepts and halts.
  • If w is not in L, then M eventually halts, although it never enters an accepting state.

If the language is recursive then it is accepted by a TM that always halts.(Decider)

A language L is recursively enumerable if for some TM , but necessary halts for all input. (Recognizer)

Not RE > RE > R

If a language is recursive, then its complement is also recursive.

If a language and its complement are both recursively enumerable, then the langauge is recursive.

A language that's not recursively enumerable

present TM as a binary string

  1. Represent state with
  2. Number the tape symbols and represent with
  3. Encode the directions L as 01 and R as 02
  4. Encode the transition as
  5. Encode the complete transition function as where the are the encodings of the individual transitions
  6. Encode the TM with final state as where T is the encoding of the transition function

diagonalization language

The language , the diagonalization language, is the set of strings such that is not in .

Because we could write every TM as binary string and binary string is countable, so we could list all TMs as whose code is .

Not all binary string could represent valid TM, of course. So we could consider them as TMs that accept no string including empty string.

Then we could construct a table that could represented the characteristic vectors of each languages. Each row means a language and each column is a string, if accept then this cell is 1 and 0 otherwise.

In order to construct , we are using the same trick in discrete math. We could find the diagonal value of this table and flip them. For example, if in the table accepts then is not in .

is not recursively enumerable

No TM could accepts .

Still the same trick in discrete math.

Suppose for some TM . Then M should be some .

If , then should accepts , but according to the def of , is not in . Contradiction.

If , then should not accepts , but according to the def of , is in . Contradiction.

So M not exists. is not recursively enumerable.

A language that's RE but not Recursive

The universal language is {m1111w | m is the encoding of a TM M and w is an input string and M accepts w}.

Universal Language is RE

We need to build a TM for it. This TM has 3 tapes.

  • 1st tape: the string content m1111w
  • 2nd tape: one track for the current string w, the other track is the pointer of the current tape symbol(this tape is to simulate the TM m)
  • 3rd tape: to record the current state of TM m

For the given string m1111w, first put it to 1st tape, then copy w to the 2nd tape and put the pointer to the start of the string. Then go back to 1st tape and read the start state then write to 3rd tape.

Then, we check the current state on 3rd tape and check the next symbol on 2nd tape, then go back to 1st tape part m to see what should do next. We could go to a final state and halt if m accepts w.

Universal Language is not Recursive

We will prove it by proving that the complement of universal language is not recursive enumerable.

Suppose the complement of universal language is recursive enumerable, then we could build a Turing Machine T for it. We then make a new TM T'(w) = T(w1111w) such that T' accepts w when T cannot accept w1111w.

Then T' should accept w when w is in diagonal language. But diagonal language is not RE, so there should be no T' or T.

Rice's Theorem: Nothing Decidable

Version 1

Let Q be any non-trivial property of recursively enumerable languages. Then Q is undecidable.

We identify a property of a language with the set of TMs that accept the languages with this property. A non-trivial property is one that applies to some but not all languages.

Version 2

Let a be any set of TM. Let

Then if is neither empty nor the set of all TM, then must be undecidable.

Proof

Let Grumpy be the TM that doesn't accept any string.

First assume doesn't include Grumpy. It is clear that isn't empty.

Let be any particular TM in . We will use the decider of to build a decider for , as follows:

Given any pair (M, w), build a new TM M', such that:

  1. If M cannot accept w, then , both M and M' cannot recognize and accept w. M' cannot accept any string that cannot accepted by M, so M' is equivalent to Grumpy and not in . However, we assumed that doesn't include Grumpy. Contradiction.
  2. If M does accept w, then , that is, M' could accept the same string as some in . So M' is in .

Then, a decider for M' could only be , which will decide if M accepts w. So it will decide universal language. So the decider of is not exist and is undecidable.