Content deleted Content added
→Example: Definition for functionals |
|||
Line 94:
:# For any computable enumeration operator Φ there is a recursively enumerable set ''F'' such that Φ(''F'') = ''F'' and ''F'' is the smallest set with this property.
:# For any recursive operator Ψ there is a partial computable function φ such that Ψ(φ) = φ and φ is the smallest partial computable function with this property.
The first recursion theorem is also called Fixed point theorem (of recursion theory). There is also a definition which can be applied to [[Primitive recursive functional|recursive functionals]] as follows:
Let <math>\Phi: \mathbb{F}(\mathbb{N}^k) \rightarrow (\mathbb{N}^k)</math> be a recursive functional. Then <math>\Phi</math> has a least fixed point <math>f_{\Phi}: \mathbb{N}^k \rightarrow \mathbb{N}</math> which is computable i.e.
1) <math>\Phi(f_{\phi})=f_{\Phi}</math>
2) <math>\forall g \in \mathbb{F}(\mathbb{N}^k)</math> such that <math>\Phi(g)=g</math> it holds that <math>f_{\Phi}\subseteq g</math>
3) <math>f_{\Phi}</math> is computable
=== Example ===
| |||