Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.theory > #11987

Proof of recursion theorem

From Newberry <newberryxy@gmail.com>
Newsgroups comp.theory, sci.logic
Subject Proof of recursion theorem
Date 2017-04-09 21:04 -0400
Organization A noiseless patient Spider
Message-ID <ocelih$ulr$1@dont-email.me> (permalink)

Cross-posted to 2 groups.

Show all headers | View raw


Let T be a Turing machine that computes a a function t: N → N. There is 
a Turing machine R that computes a number r, such that r = T(<R>).

[<R> is the description R; you can think of it as a Turing machine 
specification or source code of a program.]

R is a machine that can obtain its own description, inspect or execute 
itself.

PROOF:
We construct R as follows: R = A o B o T. This means that the output of 
A is fed to B, and the output of B is fed to T.
* A is a machine that outputs <B o T> on the tape.
* B is a machine that from input <M> computes <P_<M> o M>. P_<M> is a 
machine that outputs the description of M.
The output from A to B is <B o T>. B will transform this into <P_<B o T> 
o (B o T)>. But P_<B o T> is A. So the output from B is <A o B o T> = 
<R>. So the output from B to T is <R>, and T will compute T(<R>). QED.

I have been loosely following Sipser and this document
https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-045j-automata-computability-and-complexity-spring-2011/lecture-notes/MIT6_045JS11_lec10.pdf

We can represent the Recursion Theorem in C-like syntax. Given a 
function T() that somehow utilizes a function f() we can construct a 
function R() whose output is equal to the output of T() when R() is 
passed to T(). Here is an example in C.

int T(int f()){
     return f + 8;
};

int R(){
     T(R);
};

The outputs of R() and T(R) are identical. You can actually compile it 
and run it.

Back to comp.theory | Previous | Next — Next in thread | Find similar | Unroll thread


Thread

Proof of recursion theorem Newberry <newberryxy@gmail.com> - 2017-04-09 21:04 -0400
  Re: Proof of recursion theorem Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-04-10 14:41 +0100

csiph-web