Please provide the definitions you are using for
"recursive sets"
"recursive enumerable sets"
"Mi(i) does not accept i"
What is Mi(i)? What does it mean for it to "accept" or "not accept" i?
Recursive set: In
computability theory, a
set of
natural numbers is called
recursive,
computable or
decidable if there is an
algorithm which takes a number as input, terminates after a finite amount of time (possibly depending on the given number) and correctly decides whether the number belongs to the set or not.
Recursive enumerable set:
In
computability theory, traditionally called recursion theory, a set
S of
natural numbers is called
recursively enumerable,
computably enumerable,
semidecidable,
provable or
Turing-recognizable if:
- There is an algorithm such that the set of input numbers for which the algorithm halts is exactly S.
Or, equivalently,
- There is an algorithm that enumerates the members of S. That means that its output is simply a list of the members of S: s1, s2, s3, ... . If necessary, this algorithm may run forever.
What does Mi(i) means?
The list we need shall consist of all Turing machine descriptions in numerical
order. Composing this is easy, just go through all of the decimal integers (0, 1,
2, ...) and discard every integer that is not a Turing machine description. This
straightforward (tedious, but straightforward) process provides us with a list of machines.
Now, we merely number them according to where they appear on the list of machine descriptions. In
other words:
M1 = the first machine on the list
M2 = the second machine on the list
and so forth. This list of machines is called the standard enumeration of Turing
machines. A machine's place on the list (i.e., the subscript) is called its index. So, now we
know exactly which machine we're talking about then we mention M239 or M753. The sets
accepted by these machines are also numbered in the same manner. We call them W1, W2, and so on.
More formally:
Wi = { x | Mi(x) halts }
We have now defined a standard enumeration or listing of all the Turing machines:
M1, M2, M3, … as well as a standard enumeration of all the computable sets: W1, W2,
W3, …
