User:IssaRice/Computability and logic/K is recursively enumerable: Difference between revisions

From Machinelearning
Line 9: Line 9:
'''Proof.''' Let <math>\phi_0, \phi_1, \phi_2, \ldots</math> be a standard enumeration of the partial recursive functions.
'''Proof.''' Let <math>\phi_0, \phi_1, \phi_2, \ldots</math> be a standard enumeration of the partial recursive functions.


We can define the diagonal partial function <math>d(x) := \phi_x(x) + 1</math>. This is a partial recursive function because both <math>\phi_x</math> and <math>x \mapsto x+1</math> are, and we can obtain <math>d</math> via substitution. Thus, <math>d = \phi_e</math> for some <math>e \in \mathbf N</math>.
We can define the diagonal partial function <math>d(x) := \phi_x(x) + 1</math>. This is a partial recursive function because both <math>\phi_x</math> and <math>x \mapsto x+1</math> are, and we can obtain <math>d</math> via substitution. Thus, <math>d = \phi_e</math> for some <math>e \in \mathbf N</math>. (Actually, is it really so simple to show <math>d</math> is partial recursive? We're not just using a fixed <math>\phi_x</math>, but rather we are allowing the partial function index to move around.)


But now <math>K = \operatorname{domain} d = \operatorname{domain} \phi_e = W_e</math>. Since a set is recursively enumerable iff it is the domain of some partial recursive function, this shows that <math>K</math> is recursively enumerable.
But now <math>K = \operatorname{domain} d = \operatorname{domain} \phi_e = W_e</math>. Since a set is recursively enumerable iff it is the domain of some partial recursive function, this shows that <math>K</math> is recursively enumerable.

Revision as of 20:08, 9 January 2019

K:={x:x∈Wx}

Proofs

Finding a partial recursive function that enumerates K

This proof is from Enderton.[1]

Proof. Let ϕ0,ϕ1,ϕ2,… be a standard enumeration of the partial recursive functions.

We can define the diagonal partial function d(x):=ϕx(x)+1. This is a partial recursive function because both ϕx and x↦x+1 are, and we can obtain d via substitution. Thus, d=ϕe for some e∈N. (Actually, is it really so simple to show d is partial recursive? We're not just using a fixed ϕx, but rather we are allowing the partial function index to move around.)

But now K=domaind=domainϕe=We. Since a set is recursively enumerable iff it is the domain of some partial recursive function, this shows that K is recursively enumerable.

Discussion. The definition of d doesn't seem to be important. Actually, I think we can just take d(x)=ϕx(x). But it seems Enderton did the plus one to make a further point (namely, that it looks like we might be diagonalizing out of this class of functions, but luckily we're not, thanks to our objects only being partial functions).

Using programs

Peter Smith. An Introduction to Gödel's Theorems. p. 24.

References

  1. ↑ Herbert Enderton. Computability Theory. p. 80
Retrieved from "https://machinelearning.subwiki.org/w/index.php?title=User:IssaRice/Computability_and_logic/K_is_recursively_enumerable&oldid=1334"