5 Classical Results

Theorem

The class of Primitive Recursive functions (and extensions) does not contain all the effectively computable functions:

Proof ▼

reductio ad absurdum

1: Encode and enumerate p.r. functions	$f_{0}, \hdots, f_{n}$ . There are $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^{i} 1^{j} : i, j \geq 0 and \exists w \in L s . t | w | = i + j}$ is regular if $L$ regular T. built NFA $Q \times {0, 1}$ , $δ^{'} ((q, 0), 0) = {(δ (q, σ), 0) : σ \in Σ^{*}} . δ^{'} ((q, 0), ϵ) = {(δ (q, 1), σ) : σ \in Σ^{*}}$
$L^{'} = {0^{i} 1^{j} : i, j \geq 0 and \exists w \in L s . t | w | = | i - j |}$ is regular if $L$ regular F. take $L = ϵ$ r = r1* r2(r4+r3r1*r2)* where: r1: initial → initial r2: initial → accepting r3: accepting → initial r4: accepting → accepting

5 Classical Results

Resulting regular expres­sion:

Resulting regular expression: