User:IssaRice/Computability and logic/Rogers fixed point theorem using Sipser's notation

From Machinelearning
Revision as of 20:28, 12 July 2019 by IssaRice (talk | contribs) (Created page with "Sipser's textbook presents the recursion theorem, but not the fixed point theorem. Here is one way to state the fixed point theorem using Sipser's notation. '''Theorem''' (Fi...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Sipser's textbook presents the recursion theorem, but not the fixed point theorem. Here is one way to state the fixed point theorem using Sipser's notation.

Theorem (Fixed point theorem). Let F be a Turing machine which computes a function f:Σ*Σ*. Then there exists a Turing machine T which computes a function t:Σ*Σ*, and a Turing machine R which computes a function r:Σ*Σ*, such that f(T)=R and t(w)=r(w) for all wΣ*.