Diferencia entre revisiones de «Función de Ackermann»

* Sea <math>k \in \mathbb{N} ,\; f_{k} \in \mathrm{FRP}</math>

Además la función de Ackerman (<math> \mathrm{ACK}(x) = f_{x}(x) </math>) '''no''' es FRP (función recursiva primitiva). La demostración de este teorema se lleva a cabo por [[reducción al absurdo]] y utilizando el lema de que toda [[recursión primitiva|función recursiva primitiva]] está [[mayoración|mayorada]] por una función Ackermann.

Comenzamos suponiendo que <math> \mathrm{ACK}(x) \in \mathrm{FRP} </math>, por tanto <math> \mathrm{ACK}(x)+1 \in \mathrm{FRP} </math>

Usando el lema de la [[mayoración]], debe existir un ''k'' tal que <math> \mathrm{ACK}(x)+1 \le f_{k}(x) </math>

Pero entonces, como esto vale para todo ''x'', también valdrá para ''x''=''k''.

<math>\mathrm{ACK}(k)+1 \le f_{k}(k) </math>, usando la definición, llegamos a que:

<math>\mathrm{ACK}(k)+1 \le \mathrm{ACK}(k)</math>