5 Classical Results
The class of Primitive Recursive functions (and extensions) does not contain all the effectively computable functions:
reductio ad absurdum
|
1: Encode and enumerate p.r. functions |
\(f_0, \hdots , f_n \). There are \(\mathbb {N}\) |
|
2: Define diagonal func. \(g(x) = f_x(x)+1\) |
Intuitively computable |
|
3: \(\forall n . g(n) \neq f_n(n) \Rightarrow \forall n . g \neq f_n \) |
\(g\) doesn’t appear in list |
Implies there is no formalism for expressing only and all total functions.
Resulting regular expression:
\(L'=\{ 0^i1^j:i,j\ge 0\text{ and } \exists w \in L s.t |w|=i+j\} \) is regular if \(L\) regular T. built NFA \(Q\times \{ 0,1\} \),\(\delta '((q,0),0)=\{ (\delta (q,\sigma ),0):\sigma \in \Sigma ^*\} .\delta '((q,0),\epsilon )=\{ (\delta (q,1),\sigma ):\sigma \in \Sigma ^*\} \)
\(L'=\{ 0^i1^j:i,j\ge 0\text{ and } \exists w \in L s.t |w|=|i-j|\} \)is regular if \(L\) regular F. take \(L=\epsilon \) r = r1* r2(r4+r3r1*r2)* where: r1: initial → initial r2: initial → accepting r3: accepting → initial r4: accepting → accepting