4.4 Batallas entre paradigmas

En esta seccion compararemos los tres paradigmas de computabilidad efectiva que hemos desarrollado anteriormente. Para esto probaremos que cada uno de dichos paradigmas "vence" al otro en el sentido que incluye por lo menos todas las funciones que incluye el otro en su modelizacion del concepto de funcion Σ$\Sigma$-efectivamente computable.

4.4.1 Neumann vence a Godel

Usando macros podemos ahora probar que el paradigma imperativo de Neumann es por lo menos tan abarcativo como el funcional de Godel. Mas concretamente:

Proof. Probaremos por induccion en k$k$ que

1. (*) Si h∈RΣk$h\in R_k^{\Sigma }$, entonces h$h$ es Σ$\Sigma$-computable.

El caso k=0$k=0$ es dejado al lector. Supongamos (*) vale para k$k$, veremos que vale para k+1$k+1$. Sea h∈RΣk+1−RΣk.$h\in R_{k+1}^{\Sigma }-R_k^{\Sigma }.$ Hay varios casos

Caso 1. Supongamos h=M(P)$h=M\left(P\right)$, con P:ω×ωn×Σ∗m→ω$P:\omega \times {\omega }^n\times {\Sigma }^{\ast m}\to \omega$, un predicado perteneciente a RΣk$R_k^{\Sigma }$. Por hipotesis inductiva, P$P$ es Σ$\Sigma$-computable y por lo tanto tenemos un macro [IFP(V1,...,V¯n+1,W1,...,Wˉm)GOTOA1]$$\left[IFP\right(V1,...,V\overline{n+1},W1,...,W\overline{m}\left)GOTOA1\right]$$ lo cual nos permite realizar el siguiente programa L2[IFP(N¯n+1,N1,...,Nˉn,P1,...,Pˉm)GOTOL1]N¯n+1←N¯n+1+1GOTOL2L1N1←N¯n+1 Es facil chequear que este programa computa h.

Caso 2. Supongamos h=R(f,G), con f:S1×...×Sn×L1×...×Lm→Σ∗Ga:S1×...×Sn×L1×...×Lm×Σ∗×Σ∗→Σ∗, a∈Σ elementos de RΣk. Sea Σ={a1,...,ar}. Por hipotesis inductiva, las funciones f, Ga, a∈Σ, son Σ-computables y por lo tanto tenemos macros [W¯m+1←f(V1,...,Vˉn,W1,...,Wˉm)] [W¯m+3←Gai(V1,...,Vˉn,W1,...,Wˉm,W¯m+1,W¯m+2)], i=1,...,r Podemos entonces hacer el siguiente programa: [P¯m+3←f(N1,...,Nˉn,P1,...,Pˉm)]L¯r+1IFP¯m+1 BEGINS a1 GOTOL1            ⋮IFP¯m+1 BEGINS ar GOTOLˉrGOTOL¯r+2L1P¯m+1← ↷P¯m+1[P¯m+3←Ga1(N1,...,Nˉn,P1,...,Pˉm,P¯m+2,P¯m+3)]P¯m+2←P¯m+2.a1GOTOL¯r+1            ⋮LˉrP¯m+1← ↷P¯m+1[P¯m+3←Gar(N1,...,Nˉn,P1,...,Pˉm,P¯m+2,P¯m+3)]P¯m+2←P¯m+2.arGOTOL¯r+1L¯r+2P1←P¯m+3 Es facil chequear que este programa computa h.

El resto de los casos son dejados al lector.  

Un corolario importante de esta batalla es el:

4.4.1.1 Se lleno de macros

Cabe destacar que el Segundo Manantial de Macros nos dice que en SΣ hay macros [V¯n+1←f(V1,...,Vˉn,W1,...,Wˉm)][W¯m+1←g(V1,...,Vˉn,W1,...,Wˉm)][IFP(V1,...,Vˉn,W1,...,Wˉm)GOTOA1] para todas las funciones Σ-mixtas y predicados Σ-mixtos que hemos trabajado hasta el momento en la materia ya que todas eran Σ-p.r.. Esto fortalece mucho al lenguaje SΣ ya que ahora tenemos macros para todas las funciones y predicados cotidianos en la matematica, ademas de tener macros para todas las funciones y predicados Σ-computables, debido al Primer Manantial de Macros. Veamos un ejemplo:

Proof. Podemos suponer que ni S1 ni S2 son vacios ya que de lo contrario el resultado es trivial. Ademas supondremos que n=2 y m=1.

La idea de la prueba es la misma que la que usamos para probar que la union de conjuntos Σ-efectivamente enumerables es Σ-efectivamente enumerable. Daremos usando macros un programa que enumera a S1∪S2 y luego aplicaremos la Caracterizacion de Σ-enumerabilidad. Por hipotesis hay funciones F:ω→ω×ω×Σ∗ y G:ω→ω×ω×Σ∗ tales que F(1), F(2), F(3), G(1), G(2) y G(3) son Σ-computables, Im(F)=S1 y Im(G)=S2. O sea que nuestro Primer Manantial de Macros nos dice que en SΣ hay macros [V2←F(1)(V1)][V2←F(2)(V1)][W1←F(3)(V1)][V2←G(1)(V1)][V2←G(2)(V1)][W1←G(3)(V1)] Ya que el predicado Par=λx[x es par] es Σ-p.r., el Segundo Manantial de Macros nos dice que en SΣ hay un macro: [IF Par(V1) GOTO A1] el cual escribiremos de la siguiente manera mas intuitiva [IF V1 es par GOTO A1] Ya que la funcion D=λx[⌊x/2⌋] es Σ-p.r., el Segundo Manantial de Macros nos dice que hay un macro: [V2←D(V1)] el cual escribiremos de la siguiente manera mas intuitiva [V2←⌊V1/2⌋] Sea P el siguiente programa: [IF N1 es par GOTO L1N1←N1˙−1[N1111←⌊N1/2⌋][N1←G(1)(N1111)][N2←G(2)(N1111)][P1←G(3)(N1111)]GOTO L2L1[N1111←⌊N1/2⌋][N1←F(1)(N1111)][N2←F(2)(N1111)][P1←F(3)(N1111)]L2SKIP Es facil ver que P cumple (a) y (b) de (3) de la Caracterizacion de Σ-enumerabilidad por lo cual S1∪S2 es Σ-enumerable.  

En forma analoga a lo hecho recien, se pueden probar, copiando la respectiva idea en el paradigma de la computabilidad efectiva, los siguientes resultados:

1. - Supongamos S1,S2⊆ωn×Σ∗m son conjuntos Σ-enumerables. Entonces S1∩S2 es Σ-enumerable.

2. - Sea S⊆ωn×Σ∗m. Si S es Σ-computable, entonces S es Σ-enumerable

O sea que con el uso de nuestros poderosos macros asociados a funciones y predicados Σ-p.r. (gracias al Segundo Manatial) mas los que provee el Primer Manatial podemos simular los procedimientos efectivos realizados dentro del paradigma filosofico con programas concretos del lenguaje SΣ. Pero esto no es del todo asi, ya que los ejemplos vistos recien no hacen uso del concepto de “ejecucion de una cantidad de pasos”, idea que en muchos diseños de nuestros procedimentos efectivos es usada. Por ejemplo si queremos “copiar” dentro del paradigama imperativo la prueba del resultado

1. - Si f:Df⊆ωn×Σ∗m→ω es una funcion Σ-efectivamente computable, entonces Df es Σ-efectivamente enumerable

notaremos la dificultad de aun no poder hablar de cantidad de pasos en la ejecucion del programa que compute a f. O sea nuestro Primer Manatial nos da un macro de asignacion para f pero no es claro de como correr una expansion de dicho macro una cierta cantidad de veces. Esto lo lograremos usando macros asociados a las funciones Haltn,m, En,m# y En,m∗ las cuales se usan en la batalla Godel vence a Neumann que viene a continuacion. Estas funciones seran clave a la hora de simular con programas a procedimientos efectivos que en su funcionamiento involucran el funcionamiento de otros procedimientos efectivos.

O sea que luego de ambas batallas entre Godel y Neumann, el paradigma imperativo se vera fortalecido sustancialmente. Tambien mas adelante en la Seccion Resultados basicos presentados en paradigma recursivo veremos como los desarrollos hechos en ambas batallas entre Godel y Neumann fortalecen al paradigma funcional. Otro ejemplo de esto ultimo es la Forma Normal de Kleene donde se prueba que toda funcion Σ-recursiva es expresable en la forma g∘M(P) donde g es una funcion Σ-p.r. y P es un predicado Σ-p.r..

4.4.2 Godel vence a Neumann

Para probar que toda funcion Σ-computable es Σ-recursiva debemos hacer un profundo estudio de la recursividad del lenguaje SΣ. Primero analizaremos la recursividad de la sintaxis de SΣ.

4.4.2.1 Analisis de la recursividad de la sintaxis de SΣ

Primero probaremos dos lemas que muestran que la sintaxis de SΣ es (Σ∪Σp)-recursiva primitiva. Recordemos que Sig:Num∗→Num∗ fue definida de la siguiente manera Sig(ε)=1Sig(α0)=α1Sig(α1)=α2Sig(α2)=α3Sig(α3)=α4Sig(α4)=α5Sig(α5)=α6Sig(α6)=α7Sig(α7)=α8Sig(α8)=α9Sig(α9)=Sig(α)0 Y tambien definimos Dec:ω→Num∗ de la siguiente manera Dec(0)=εDec(n+1)=Sig(Dec(n)) Recordemos tambien que para hacer mas agil la notacion escribimos ˉn en lugar de Dec(n).

Proof. Es facil ver que Dec es Num-p.r.. Ya que tambien es (Σ∪Σp)-mixta, el Teorema 4.2 nos dice que es (Σ∪Σp)-p.r.. En el Lema 4.12 se da una prueba facil de este hecho, sin recurrir al citado teorema.  

Proof. Para simplificar la prueba asumiremos que Σ={@,▴}. Ya que InsΣ es union de los siguientes conjuntos L1={Nˉk←Nˉk+1:k∈N}L2={Nˉk←Nˉk˙−1:k∈N}L3={Nˉk←Nˉn:k,n∈N}L4={Nˉk←0:k∈N}L5={IFNˉk≠0GOTOLˉm:k,m∈N}L6={Pˉk←Pˉk.@:k∈N}L7={Pˉk←Pˉk.▴:k∈N}L8={Pˉk← ↷Pˉk:k∈N}L9={Pˉk←Pˉn:k,n∈N}L10={Pˉk←ε:k∈N}L11={IFPˉkBEGINS@GOTOLˉm:k,m∈N}L12={IFPˉkBEGINS▴GOTOLˉm:k,m∈N}L13={GOTOLˉm:m∈N}L14={SKIP}L15={Lˉkα:k∈Ny α∈L1∪...∪L14} solo debemos probar que L1,...,L15 son (Σ∪Σp)-p.r.. Veremos primero por ejemplo que L11={IFPˉkBEGINS@GOTOLˉm:k,m∈N} es (Σ∪Σp)-p.r.. Primero notese que α∈L11 si y solo si existen k,m∈N tales que α=IFPˉkBEGINS@GOTOLˉm Mas formalmente tenemos que α∈L11 si y solo si (∃k∈N)(∃m∈N)α=IFPˉkBEGINS@GOTOLˉm Ya que cuando existen tales k,m tenemos que ˉk y ˉm son subpalabras de α, el lema anterior nos dice que α∈L11 si y solo si (∃k∈N)k≤10|α|(∃m∈N)m≤10|α|α=IFPˉkBEGINS@GOTOLˉm Sea P=λmkα[α=IFPˉkBEGINS@GOTOLˉm] Ya que Dλk[ˉk]=ω, tenemos que DP=ω2×(Σ∪Σp)∗. Notese que P=λαβ[α=β]∘[p2,13,f] donde f=λα1α2α3α4[α1α2α3α4]∘[C2,1IFP,λk[ˉk]∘p2,12,C2,1BEGINS@GOTOL,λk[ˉk]∘p2,11] lo cual nos dice que P es (Σ∪Σp)-p.r..

Notese que χ(Σ∪Σp)∗L11=λα[(∃k∈N)k≤10|α|(∃m∈N)m≤10|α|P(m,k,α)] Esto nos dice que podemos usar dos veces el Lema 4.22 para ver que χ(Σ∪Σp)∗L11 es (Σ∪Σp)-p.r.. Veamos como. Sea Q=λkα[(∃m∈N)m≤10|α|P(m,k,α)] Por el Lema 4.22 tenemos que λxkα[(∃m∈N)m≤xP(m,k,α)] es (Σ∪Σp)-p.r. lo cual nos dice que Q=λxkα[(∃m∈N)m≤xP(m,k,α)]∘[λα[10|α|]∘p1,12,p1,11,p1,12] lo es. Ya que χ(Σ∪Σp)∗L11=λα[(∃k∈N)k≤10|α|Q(k,α)] podemos en forma similar aplicar el Lema 4.22 y obtener finalmente que χ(Σ∪Σp)∗L11 es (Σ∪Σp)-p.r..

En forma similar podemos probar que L1,...,L14 son (Σ∪Σp)-p.r.. Esto nos dice que L1∪...∪L14 es (Σ∪Σp)-p.r.. Notese que L1∪...∪L14 es el conjunto de las instrucciones basicas de SΣ. Llamemos InsBasΣ a dicho conjunto. Para ver que L15 es (Σ∪Σp)-p.r. notemos que χ(Σ∪Σp)∗L15=λα[(∃k∈N)k≤10|α|(∃β∈InsBasΣ)|β|≤|α|α=Lˉkβ] lo cual nos dice que aplicando dos veces el Lema 4.22 obtenemos que χ(Σ∪Σp)∗L15 es (Σ∪Σp)-p.r.. Ya que InsΣ=InsBasΣ∪L15 tenemos que InsΣ es (Σ∪Σp)-p.r..  

Recordemos que Bas:InsΣ→(Σ∪Σp)∗, fue definida por Bas(I)={Jsi I es de la forma LˉkJ, con k∈N y J∈InsΣIcaso contrario Definamos Lab:InsΣ→(Σ∪Σp)∗ de la siguiente manera Lab(I)={Lˉksi I es de la forma LˉkJ, con k∈N y J∈InsΣεcaso contrario

Proof. Sea ≤ un orden total sobre Σ∪Σp. Sea L={Lˉk:k∈N}∪{ε}. Dejamos al lector probar que L es un conjunto (Σ∪Σp)-p.r.. Sea P=λIα[α∈InsΣ∧I∈InsΣ∧[α]1≠L∧(∃β∈L) I=βα] Note que DP=(Σ∪Σp)∗2. Dejamos al lector probar que P es (Σ∪Σp)-p.r.. Notese ademas que cuando I∈InsΣ tenemos que P(I,α)=1 sii α=Bas(I). Dejamos al lector probar que Bas=M≤(P) por lo que para ver que Bas es (Σ∪Σp)-p.r., solo nos falta ver que la funcion Bas es acotada por alguna funcion (Σ∪Σp)-p.r. y (Σ∪Σp)-total. Pero esto es trivial ya que |Bas(I)|≤|I|=λα[|α|](I), para cada I∈InsΣ.

Finalmente note que Lab=M≤(λIα[αBas(I)=I]) lo cual nos dice que Lab es (Σ∪Σp)-p.r..  

Recordemos que dado un programa P habiamos definido IPi=ε, para i=0 o i>n(P). O sea que la funcion (Σ∪Σp)-mixta λiP[IPi] tiene dominio igual a ω×ProΣ. Notese que usamos notacion lambda respecto del alfabeto Σ∪Σp. Ademas notese que usamos la variable P en la notacion lambda por un tema de comodidad psicologica dado que la expresion Iαi esta definida solo cuando α es un programa pero podriamos haber escrito λiα[Iαi] y sigue siendo la misma funcion.

Proof. Ya que ProΣ=DλP[n(P)] tenemos que (b) implica (a). Para probar (b) Sea ≤ un orden total sobre Σ∪Σp. Sea P el siguiente predicado

λx[Lt(x)>0∧(∀t∈N)t≤Lt(x)∗≤((x)t)∈InsΣ∧

            (∀t∈N)t≤Lt(x)(∀m∈N)¬(Lˉm t-final ∗≤((x)t))∨

                 (∃j∈N)j≤Lt(x)(∃α∈(Σ∪Σp)−Num)Lˉmα t-inicial∗≤((x)j)]

Notese que DP=N y que P(x)=1 sii Lt(x)>0, ∗≤((x)t)∈InsΣ, para cada t=1,...,Lt(x) y ademas ⊂t=Lt(x)t=1∗≤((x)t)∈ProΣ. Para ver que P es (Σ∪Σp)-p.r. solo nos falta acotar el cuantificador (∀m∈N) de la expresion lambda que define a P. Ya que nos interesan los valores de m para los cuales ˉm es posiblemente una subpalabra de alguna de las palabras ∗≤((x)j), el Lema 4.44 nos dice que una cota posible es 10max{|∗≤((x)j)|:1≤j≤Lt(x)}−1. Dejamos al lector los detalles de la prueba de que P es (Σ∪Σp)-p.r.. Sea Q=λxα[P(x)∧α=⊂t=Lt(x)t=1∗≤((x)t)]. Note que DQ=N×(Σ∪Σp)∗. Claramente Q es (Σ∪Σp)-p.r.. Ademas note que DM(Q)=ProΣ. Notese que para P∈ProΣ, tenemos que M(Q)(P) es aquel numero tal que pensado como infinitupla (via mirar su secuencia de exponentes) codifica la secuencia de instrucciones que forman a P. Es decir M(Q)(P)=⟨#≤(IP1),#≤(IP2),...,#≤(IPn(P)),0,0,...⟩ Por (b) del Lema 4.25, M(Q) es (Σ∪Σp)-p.r. ya que para cada P∈ProΣ tenemos que M(Q)(P)=⟨#≤(IP1),#≤(IP2),...,#≤(IPn(P)),0,0,...⟩=n(P)Πi=1pr(i)#≤(IP1)≤|P|Πi=1pr(i)#≤(P) Ademas tenemos que λP[n(P)]=λx[Lt(x)]∘M(Q)λiP[IPi]=∗≤∘g∘[p1,11,M(Q)∘p1,12] donde g=C1,10|{0}×ω∪λix[(x)i], lo cual dice que λP[n(P)] y λiP[IPi] son funciones (Σ∪Σp)-p.r..  

4.4.2.2 Analisis de la recursividad de la semantica de SΣ

Para estudiar la recursividad de la semantica de SΣ deberemos definir varias funciones que tienen que ver con el funcionamiento de un programa y estudiar su recursividad.

Las funciones in,m, En,m# y En,m∗

Sean n,m≥0 fijos. Definamos entonces las funciones in,m:ω×ωn×Σ∗m×ProΣ→ωEn,m#:ω×ωn×Σ∗m×ProΣ→ω[N]En,m∗:ω×ωn×Σ∗m×ProΣ→Σ∗[N] de la siguiente manera (in,m(0,→x,→α,P),En,m#(0,→x,→α,P),En,m∗(0,→x,→α,P))=(1,(x1,...,xn,0,...),(α1,...,αm,ε,...))(in,m(t+1,→x,→α,P),En,m#(t+1,→x,→α,P),En,m∗(t+1,→x,→α,P))=SP(in,m(t,→x,→α,P),En,m#(t,→x,→α,P),En,m∗(t,→x,→α,P)) Notese que (in,m(t,→x,→α,P),En,m#(t,→x,→α,P),En,m∗(t,→x,→α,P)) es la descripcion instantanea que se obtiene luego de correr P una cantidad t de pasos partiendo del estado ((x1,...,xn,0,...),(α1,...,αm,ε,...)) Es importante notar que si bien in,m es una funcion (Σ∪Σp)-mixta, ni En,m# ni En,m∗ lo son.