Recursively Enumerable (RE) Sets of numbers
Key idea: Sets that are equivalent to all PC functions of
one argument.
Definitions:
Let g(X) be a PC function of one
argument.
Let
S = {n | g(n) is defined}
This set is RE.
Let P(X) be a computable predicate.
Let
S = {n | P(n) is true}
Then, this set is Recursive
Observe following characteristics of RE sets:
1. A set is Recursive if and only if it and its complement
are RE.
2. If two sets R and S are RE then the following is each
RE:
their Union
their Intersection
3. An RE set may not be Recursive.
4. The Membership question: Predicate Member(R,x)
Given a set R and a possible member x, the question of
whether or not x is indeed
a
member of the set
Member(R,x)
is computable if R is Recursive but not if R is RE (not always)
Enumeration
of all RE sets
Let Wn = { x | f (x,n) is defined}
Note
that above set Wn is RE and
it DOES correspond to a PC function of one argument
computed
by a program whose number is n.
Also
that when a program has more than one input variable,
we can
assume that the program computes a PC function of just one argument
by
assuming that only one input variable actually takes on an input value and
all other
input variables are zero initially.
All
non-negative integers represent
a. all programs with any number of input variables.
b. all PC functions of any number of arguments.
c. all PC functions of exactly one argument.
d. all RE sets of numbers:
W0 , W1 , W2 , W3 , …, Winfinity
As
above enumeration certainly contains all RE sets of numbers, for any given RE
set R,
it is the
case that there is at least one k such that
R = Wk
Now
we would like to identify a set that is RE but not Recursive.
Consider
a set: K = {x | x is in Wx
}
That
is, if j is in this set K, it is also in its corresponding RE set, Wj
as we can
have any number j corresponding to the set Wj
Now,
we claim that the complement of this set K is not RE,
and hence
K is not Recursive while it is RE.
THM4.7
(page-82) just says that.
The
set K is RE but not Recursive.
Proof:
(By contradiction)
Assume
that ~K is RE.
So,
there must an integer j such that ~K =
Wj
Look
us look at this integer j (as it is suspicious)
There
are two possibilities regarding its belonging:
Case-1: j is in Wj
Case-2: j is not in Wj
Case-1: j is in Wj so it must be in K by the definition of the
set K
But we are assuming that it is not in K by the
definition of Wj
A contradiction.
Case-2:
j is not in Wj
, so it must not be in K from the def of the set K.
But we are assuming that it is in K
from the def of Wj
Again, a
contradiction.
QED.
Equivalence
among Ranges of functions:
THM4.11
(page-84)
Let R be a non-empty RE sets.
The following are all the same:
The set R
The range of a certain PR
function.
The range of a certain
Computable function.
The range of a certain PC
function.
This comes from THM 4.8, THM4.9 and THM 4.10
1. THM 4.8
For any RE set B, we have the following equality:
B =
{x | (%t) R(x,t)) for a PR predicate.
(Because R(x,t)
can be STP(x,y,t) where y is the program
corresponding to
this
RE set B and this STP() is PR)
2. THM4.9
For any non-empty RE set B, we have the following equality:
B = {f(n) for n=0,1,2,3, ...,
infinity} for a certain PR function.
(That is, B is the range of this PR function)
Key for the Proof: Using above PR predicate R(x,t) and picking an arbitrary
element, say k, of this RE set B
(since this set B is nonempty).
We define the needed PR function f(x) as follows:
f(x) = l(x) if R(l(x),r(x))
k otherwise
a. This function is PR. (We used
Definition-by-Cases Operation)
b. Every f(x) is in this set B, from the very def
of this function above.
c. Every element of B is the same as f(x) for some
x.
Let k be in B.
Then R(k,t) is true for some t, and hence k is f(<k,t>)
If R(k,t) is true
R(l<k,t>, r<k,t>)
is true and
f(<k,t>) is the
same as l(<k,t>) which k
3. THM4.10
For any PC function, f(x), we have a certain RE set B
such that B = {f(x) | f(x) is
defined}, that is, the set B is the same as
the range of this PC function.
Key idea for proof:
Find
a corresponding PC function to this RE set we need.
Define a function g(x) = 1 if x is in
B, namely if x is f(u) for some u
= undefined
otherwise, that is, if x is not in B.
Now,
if this function g() is PC, then the set B is RE by
the definition of
RE sets.
All
we have to do is to show that g() is PC, namely, find
a program.
Key idea for constructing this
Program:
Given an input X, this program must
check whether a program q
computing the
PC function f(u) stops (by possibly indefinitely
incrementing
the step counter of the STP()) for any u and when
the program q
stops it checks to see if the input X is the same as f(u).
This program stops only when
1. the
program q stops for a certain input u of its own and
2. the input
X is the same as f(u) computed by q.
So, this program must increment two
values, x and t, in repeatedly checking
STP(x,q,t) for checking the program q stops.
Note
that as long as the ranges of functions are concerned, PC functions are
no different from PR functions or
from Computable functions, as a group.
THM5.1 (Parameter Theorem): Page-83
Key
idea: Finding a systematic way of
eliminating any number of arguments of a
function while preserving the identity of the function.
The resulting new function with fewer arguments is a very special
case of the original function.
For
any n and m>=1, we have
f (X1,X2, ..., Xm, U1, U2, ..., Un,
y) =
f (X1,X2, ..., Xm,
Snm (U1,U2, ..., Un, y))
where Snm (U1,U2, ..., Un, y)
is PR.
Note
that while the LHS of above equality shows a Universal function for functions
of m+n arguments the RHS shows one of m arguments.
An Example of non-RE set
Let TOT =
{y | ($x) f
(x,y) is
defined}
So,
this is the set of all programs that compute a total function (hence a
Computable), each.
THM6.1 (page-90)
The set TOT is not RE.
Proof: By contradiction.
1. Assuming that it
were RE.
2. There is a
computable function g(x) since TOT is not empty such that
TOT = {g(0), g(1), g(2), g(3), ..., } and every program computing a
computable
function of one argument is g(k), for some k, and is in this
set.
Trick: Define a Computable function whose program cannot be
in this set (and list).
3. Let h(x) = f (x, g(x)) + 1 which is a function of one argument and
by definition
it is computable.
4. Let p be the
number of a program that computes this function h(x).
5. We claim that there is no k such that g(k)
= p
So, this function
h(x) is not computable, which is a contradiction.
6. Now, how we claim
that there is no k such that p = g(k)
Suppose that
there were a number k such that p=g(k) that is, the
program p
computes a total function.
Let look at the fate
of this mysterious number k.
a. h(k) = f (k, g(k)) + 1 from def of h(x)
b. h(k) = f (k, p) = f (k, g(k)) from the def of universal functions.