Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| 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.
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
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