Acceptance and Decidability

Notation:

In order to avoid some set-theoretic difficulties, we identify the the "class" of Turing Machines with the set of TPL programs.

We also identifying a natural number with the string "SSSS" (the concatination of symbols S) .

We can identify each subset with a set of strings in one symbol, "S" . We use to denote this language.

Lemma:

Recalling that denotes the language accepted by the Turing Machine , the set of languages, is countable. In particular, we can define a one to one map

Proof:

Do a Recursive search through all possible strings in TPL symbols and Recursively Enumerate all strings that are accepted as TPL programs.

______________________________________________________

Theorem:

There exists a subset such that there does not exist a Turing Machine with There are languages that are not accepted by Turing machines.

Proof:

Almost by definition, the set of languages , , is in one to one correspondence with the set , but by the lemma above the set of languages , , is in one to one correspondence with and, from the previous section there is no onto map .

_________________________________________________

Theorem:

There is no Turing Machine such that S if Turing Machine halts on input

and if Turing Machine loops on input

Proof:

Consider the Turing Machine defined by the following transitions:

SS

Now consider, the Turing Machine Where Suppose , we want to compute where

Suppose

S

That is halts on input . Then

S loops on input . Remember is identified with in

Suppose

That is loops on input . Then halts on input .