LENGUAJES.MAQUINAS DE TURING

LENGUAJES LIBRES DE CONTEXTO Y AUTÓMATAS

Para cualquier lenguajelibre de contexto L existe un autómata de pila $\mbox{\it AutP\/}=(Q,\mbox{\it Ent\/},\mbox{\it AlfP\/},\mbox{\it tran\/},q_0,X,\emptyset)$que reconoce al lenguaje, i.e.: libre decontexto y sea G una gramática libre de contexto que lo genere.Supongamos por un momento que la palabra vacía no pertenezca al lenguaje L.Podemos pues suponer que la gramática G=(V,T,P,S)está en forma normal de Greibach. Sea $\mbox{\it AutP\/}=(Q,\mbox{\it Ent\/},\mbox{\it AlfP\/},\mbox{\it tran\/},q_0,X,F)$donde

\begin{eqnarray*}Q=\{q_0\} &:& \mbox{\rm consta de un \'unico estado,} \\\mbo......olo \lq\lq inicial'' para la pila es el inicial de la gram\'atica.}\end{eqnarray*}


La función del autómata definido es la de simular derivaciones siniestras, enla gramática G, de palabras en el lenguaje L. De hecho, se puededemostrar que se cumple la equivalencia

\begin{displaymath}G\vdash \left(S\stackrel{*}{\Rightarrow}\sigma\right)\ \Leftr......el{*}{\Rightarrow}q_0\mbox{\it nil\/};\mbox{\it nil\/}\right)\end{displaymath}


(La implicación `` $\Rightarrow)$'' se demuestra medianteinducción en el número de producciones utilizadas en una derivación siniestrade $\sigma$. El recíproco `` $\Leftarrow )$'' se demuestra medianteinducción en el número de transiciones aplicadas para derivar la descripciónfinal $q_0\mbox{\it nil\/};\mbox{\it nil\/}$apartir de la inicial $q_0\sigma;X_0$en $\mbox{\it AutP\/}$.) Ahora bien, si Lcontuviera a la palabra vacía $\mbox{\it nil\/}$, entonces, anulemosa todas las producciones- $\mbox{\it nil\/}$, o anulables, enuna gramática que genere a $G_1=G-\{nil\}$y apliquemos loanterior para encontrar un autómata de pila $\mbox{\it AutP\/}_1$que reconozca a G1.Ampliemos, finalmente, a $\mbox{\it AutP\/}_1$añadiendo latransición $(q_0,\mbox{\it nil\/})\in\mbox{\it tran\/}(q_0,\mbox{\it nil\/},S)$.

 

 

 

 

 

 

 

Arboles y gramaticas

Sea G=(V,T,P,s0)una gramática libre de contexto. Un árbolgramatical en G es un árbol ordenado $\mbox{\it Ar\/}$tal que

  • los vértices de $\mbox{\it Ar\/}$están etiquetados con etiquetas en el alfabeto de la gramática $V\cup T$o con la etiqueta vacía, $\mbox{\it nil\/}$, y
  • cada vértice interior corresponde a una producción en G, es decir, si A es la etiqueta del vértice interior v0 y $\sigma=[e(v)\vert v\mbox{\rm es hijo de }v_0]$es la palabra formada por las etiquetas de los hijos de v0 entonces $(A\rightarrow\sigma)$es una producción en P.

Un árbol gramatical es de derivación si su raiz está etiquetada conel símbolo inicial s0 y todas sus hojas tienen etiquetasterminales o vacía. La leyendade un árbol de derivación es la palabra obtenida al concatenar ordenadamente,con cualquier orden de izquierda a derecha, las etiquetas de sus hojas. Asípues, todo árbol de derivación tiene como leyenda una palabra en L(G).Recíprocamente, para cada palabra $\sigma$en L(G) existeun árbol de derivación cuya leyenda coincide con $\sigma$. Si $\sigma=\sigma_1A\sigma_2$y $\tau=\sigma_1\beta\sigma_2$, donde $(A\rightarrow\beta)$es una producciónen P y $\sigma_2$consiste únicamente desímbolos terminales, decimos que $\tau$se sigue de $\sigma$por la aplicación diestra de una producción. Una derivaciónes diestra si todas lasaplicaciones de producciones hechas son diestras. Las derivaciones siniestras se definen simétricamente. Ejemplo. Consideremos las siguientesproducciones:

\begin{displaymath}\begin{array}{rrcll}1. & S &\rightarrow& a &\mbox{\it\begin......es cerrado por concatenaci\'on.\end{minipage}\/}\end{array}\end{displaymath}


Sendas derivacionessiniestra y diestra de la palabra a(ba2)2=abaabaason las siguientes:

\begin{displaymath}\begin{array}{\vert\vert l\vert\vert r\vert\vert}\hline \hlin......ay}abaa \\abaabaa & abaabaa \\\hline \hline\end{array}\end{displaymath}


 

 

 

 

 

 

 

 

 

 

 

 

 

En el lenguaje L(G)generado por esta gramática se encuentran incluidos los siguientes lenguajes:

  • $\{a^{3n+1}\vert n\geq 0\}$. De hecho, $L(G)\cap a^*=\{a^k\vert k\equiv1\mbox{\rm mod }3\}$.
  • $\{a^nbxa\vert n\geq 0,(n\equiv1\mbox{\rm mod }3\Rightarrow x=a),(n\not\equiv1\mbox{\rm mod }3\Rightarrow x=aa)\}$. De hecho, $G\vdash S\stackrel{*}{\rightarrow}a^nbxS$, con $n\geq 0$y x como antes.
  • $\left\{\pi_n\right\}_{n\geq 1}$, donde $\pi_n=aba^2b\cdots ba^nbx_n$y

\begin{displaymath}x_n=\left\{\begin{array}{ll}aaa &\mbox{\rm si $n\equiv 0\mb...... }3$, } \\aa &\mbox{\rm en otro caso. }\end{array}\right.\end{displaymath}





Para concluir esta sección presentaremos las nociones de ambigüedad en gramáticas. Una gramáticalibre de contexto G=(V,T,P,s0) sedice ser ambigua si algunapalabra de su lenguaje, $\sigma\in L(G)$posee dos derivacionesdiestras. Ejemplos. 1. Lagramática G cuyas producciones son $S\rightarrow SbS\vert a$es ambiguapues la palabra (ab)2a posee dos derivacionesdiestras:

\begin{displaymath}\begin{array}{\vert\vert l\vert\vert l\vert\vert}\hline \hlin......\end{array} \\ababa & ababa \\\hline \hline\end{array}\end{displaymath}





2. Si para la gramática G=(V,T,P,s0)incluimos una copia V' del conjunto de variables no-iniciales más copiasde las producciones de P con símbolos en S' entonces la nuevagramática $G'=(V\cup V', T, P\cup P', s_0)$esambigua pues cada derivación diestra puede derivarse considerando símbolos en Vo en su contraparte V'.

 

 

 

Forma normal de Chomsky

Una gramática libre decontexto G=(V,T,P,S) se dice estar en forma normal de Chomsky si susproducciones son de cualquiera de las dos formas

  • $X\rightarrow YZ$con $X,Y,Z\in V$, o bien
  • $X\rightarrow a$con $X\in V$y $a\in T$.

Proposición 3.1   Toda gramática libre de contexto G=(V,T,P,S)que no genere a la palabra vacía se puede transformar en una gramática libre decontexto G'=(V',T,P',S') en forma normal deChomsky.

En efecto, dada unagramática G, apliquemos el último procedimiento de la sección anteriorpara transformar a G en una gramática G'' sin variables inútilesni producciones vacías ni producciones unitarias equivalente a G. A lasproducciones que quedasen de la forma $X\rightarrow a$con $X\in V$y $a\in T$las dejamos sin cambio alguno.A cada producción de la forma $X\rightarrow \xi_1\xi_2\cdots\xi_k$,con $\xi_1\xi_2\cdots\xi_k\in (V+T)^*$y $k\geq 2$, la transformamos en unasucesión de producciones de la forma siguiente: A cada símbolo terminal $a\in T$que aparezca en la palabra $\xi_1\xi_2\cdots\xi_k$le asociamosuna variable nueva Xa e incorporamos la producción $X_a\rightarrow a$. Así pues lasproducciones que no sean de la forma $X\rightarrow a$con X variabley a terminal, han de ser de la forma $X\rightarrow X_1X_2\cdots X_k$, con $X, X_1X_2\cdots X_k$todos variables.Para cada una de estas últimas producciones introducimos k-2 nuevasvariables $Y_1,\ldots Y_{k-2}$e incorporamos lasucesión de producciones

\begin{displaymath}\begin{array}{lcl}X &\rightarrow& X_1Y_1 \\Y_1 &\rightar......2}Y_{k-2} \\Y_{k-2} &\rightarrow& X_{k-1}X_{k}\end{array}\end{displaymath}


Forma normal de Greibach

Una gramática libre decontexto G=(V,T,P,S) se dice estar en forma normal de Greibach si susproducciones son de la forma

\begin{displaymath}X\rightarrow a\sigma\ \ \mbox{\rm con }X\in V,a\in T,\sigma\in V^*.\end{displaymath}


Veremos que la construcciónde formas normales de Greibach equivalentes a gramáticas dadas esprocedimental. Para cualquier gramática libre de contexto G, definamos,para cada variable $X\in V$, a los conjuntossiguientes:

\begin{eqnarray*}P(X) &=&\{\mbox{\rm producciones en $G$\space cuyo antecedente ......ghtarrow\ \exists \xi\in (V+T)-\{X\},\gamma':\gamma=\xi\gamma'\end{eqnarray*}


Primeramente observemos que podemos ``componer producciones'' de manera quetengamos siempre una gramática equivalente a la gramática dada.

Lema 3.1 (Composiciónde producciones)   Si $(X\rightarrow \alpha_1Y\alpha_2)$esuna producción en G y las producciones en P(Y) puedenescribirse como $Y\rightarrow \beta_1\vert\cdots\vert\beta_m$entoncesal sustituir $(X\rightarrow \alpha_1Y\alpha_2)$porlas producciones $(X\rightarrow \alpha_1\beta_1\alpha_2\vert\cdots\vert\alpha_1\beta_m\alpha_2)$, obtenemos una gramática equivalente a G.

En efecto, en todaderivación terminal que aplique en un momento la producción $(X\rightarrow \alpha_1Y\alpha_2)$,necesariamente se ha de aplicar una producción en P(Y) parasuprimir el símbolo Y.

Lema 3.2(Transformación de producciones ``reflexivas'')   Para cada variable $X\in V$enumeremos Q(X)y R(X) como

\begin{eqnarray*}Q(X) &=& \left(X\rightarrow X\gamma_1\vert\cdots\vert X\gamma_q......) &=& \left(X\rightarrow \beta_1\vert\cdots\vert\beta_r\right)\end{eqnarray*}


Sea Z una variable que no ocurra en V. Sea $G_X=\left(V\cup\{Z\},T,P_X,S)\right)$lagramática que se obtiene al sustituir el conjunto de producciones P(X)por las producciones

\begin{displaymath}\begin{array}{rcl}X &\rightarrow& \beta_1\vert\cdots\vert\b...... &\rightarrow& \gamma_1Z\vert\cdots\vert\gamma_qZ\end{array}\end{displaymath}


 

 

 

En efecto, toda derivaciónsiniestra, en la gramática original, de una palabra en L(G) ha dedeterminar una derivación diestra de la misma palabra en la gramáticatransformada. La demostración de la afirmación anterior es directa. Como merailustración, consideremos tan solo un ejemplo: La gramática con producciones $\{S\rightarrow SAb\vert b,\ A\rightarrow ASa\vert a\}$generaal lenguaje consistente de las palabras de la forma b(ab)*.De acuerdo con la construcción anterior, como $Q(S)=\{S\rightarrow SAb\}$y $R(S)=\{S\rightarrow b\}$, obtenemosla gramática

\begin{displaymath}\begin{array}{rcl}S &\rightarrow& b \\S &\rightarrow& bZ \\Z &\rightarrow& Ab \\Z &\rightarrow& AbZ\end{array}\end{displaymath}


Presentemos sendasderivaciones, siniestra en la gramática original y diestra en la transformada,para la palabra bababab:

\begin{displaymath}\begin{array}{\vert\vert c\vert\vert c\vert\vert}\hline \hlin......abab \\bababab\end{array}\\ \hline \hline\end{array}\end{displaymath}


Veamos ahora el resultadoprincipal de esta sección:

Toda gramática libre decontexto G=(V,T,P,S) que no genere a lapalabra vacía se puede transformar en una gramática libre de contexto G*=(V*,T,P*,S*)en forma normal de Greibach.

Sea pues G=(V,T,P,S)una gramática libre de contexto que no genere a $\mbox{\it nil\/}$. La transformacióna una forma normal de Greibach la hacemos gradualmente mediante los pasossiguientes:

1.

SeaG'=(V',T,P',S') la forma normal de Chomskyde G.

2.

Modificaremos a lasproducciones en P' para tenerlas tales que toda producción, cuyoconsecuente se inicie con una variable, ha de ser de la forma $X_i\rightarrow X_j\sigma$con j>i,para un cierto orden en el conjunto de variables actuales, digamos $V''=\{X_1,\ldots,X_m\}$.

 

 

Ahora,hecha la transformación anterior, se tiene que

·       la últimavariable Xm sólo puede ser antecedente de producciones cuyosconsecuentes se inician con símbolos terminales,

·       las produccionesen P(Xm-1) cuyos consecuentes se iniciancon Xm pueden transformarse, siguiendo el lema  de``Composición de producciones'', en producciones equivalentes cuyos consecuentesse inician con símbolos terminales,

·       de manerasucesiva para i=m-2 hasta i=1 las producciones en P(Xi)cuyos consecuentes se inician con algún Xj, con j>i,pueden transformarse, siguiendo el lema  de ``Composición deproducciones'', en producciones equivalentes cuyos consecuentes se inician consímbolos terminales.

Contodas estas transformaciones la gramática resultante G*=(V*,T,P*,S*)es, en efecto, equivalente a G y está en forma normal de Greibach.



Ejemplo:

Consideremos la gramática con símbolos variables $V=\{X_1,X_2,X_3\}$y producciones
$\begin{array}{lrcl}1. & X_1 &\rightarrow& X_2X_3 \\2. & X_2 &\rightarrow& X_3X_1\vert b \\3. & X_3 &\rightarrow& X_1X_2\vert a\end{array}$
la cual ya está en forma normal de Chomsky. Transformémosla de acuerdo con elprocedimiento anterior. Observemos que las dos primeras producciones ya tienenel tipo de las buscadas en el paso 2. del procedimiento anterior. La terceratiene un consecuente que se inicia con un símbolo variable anterior al de supropio antecedente. Compongamos pues la producción 3. con la 1. Obtenemos
$\begin{array}{lrcl}4. & X_3 &\rightarrow& X_2X_3X_2\vert a\end{array}$
la cual también tiene un consecuente que se inicia con un símbolo variableanterior al de su propio antecedente. Compongamos pues la producción 4. con la2. Obtenemos
$\begin{array}{lrcl}5. & X_3 &\rightarrow& X_3X_1X_3X_2\vert bX_3X_2\vert a\end{array}$
la cual es del tipo ``reflexivo''. Para transformarla, introduzcamos una nuevavariable Y3. Obtenemos
$\begin{array}{lrcl}6. & X_3 &\rightarrow& bX_3X_2Y_3\vert aY_3\vert bX_3X_2\vert a \\7. & Y_3 &\rightarrow& X_1X_3X_2Y_3\vert X_1X_3X_2\end{array}$Con esto terminamos el paso 2. delprocedimiento anterior. El conjunto actual de producciones consta de lasproducciones 1., 2., 6. y 7. Pasemos pues al paso 3. del procedimiento.Sustituyendo 6. en 2. obtenemos
$\begin{array}{lrcl}8. & X_2 &\rightarrow& bX_3X_2Y_3X_1\vert aY_3X_1\vert bX_3X_2X_1\vert aX_1\vert b\end{array}$Sustituyendo 8. en 1. obtenemos
$\begin{array}{lrcl}9. & X_1 &\rightarrow& bX_3X_2Y_3X_1X_3\vert aY_3X_1X_3\vert bX_3X_2X_1X_3\vert aX_1X_3\vert bX_3\end{array}$Sustituyendo . en . obtenemos 10 nuevasproducciones
$\begin{array}{lrcl}7. & Y_3 &\rightarrow& \begin{array}[t]{rr}\begin{array}[t......ert \\ aX_1X_3X_3X_2\vert \\ bX_3X_3X_2 \\end{array}\end{array}\end{array}$En resumen, la gramática equivalente, enforma normal de Greibach, tiene como conjunto de variables a $V=\{X_1,X_2,X_3,Y_3\}$y susproducciones son la 6., 8., 9. y 10.:

\begin{eqnarray*}X_1 &\rightarrow& bX_3X_2Y_3X_1X_3\vert aY_3X_1X_3\vert bX_3X_2...... \\ aX_1X_3X_3X_2\vert \\ bX_3X_3X_2 \\end{array}\end{array}\end{eqnarray*}




Ejemplo ``Cadenas equilibradas deparéntesis'':

Consideremos la gramática $S\rightarrow ()\vert SS\vert(S)$quegenera a las cadenas equilibradas de paréntesis (CEP). La forma normal deChomsky de la gramática dada es
$\begin{array}{llcl}1. & S &\rightarrow& SS\vert P_{\mbox{\scriptsize\it Izq}}......arrow& ) \\4. & A &\rightarrow& SP_{\mbox{\scriptsize\it Der}}\end{array}$Consideremos el siguiente orden de lasvariables: $S,A,P_{\mbox{\scriptsize\it Izq}},P_{\mbox{\scriptsize\it Der}}$.La producción 1. es ``reflexiva''. Introduzcamos una nueva variable, X1.Al hacer la transformación pertinente, obtenemos:
$\begin{array}{llcl}5. & S &\rightarrow& P_{\mbox{\scriptsize\it Izq}}P_{\mbox......box{\scriptsize\it Izq}}A \\6. & X_1 &\rightarrow& SX_1\vert S\end{array}$La producción 4. tiene un consecuente que seinicia con una variable anterior a su antecedente. Al componer 4. con 5. obtenemos
$\begin{array}{llcl}7. & A &\rightarrow& P_{\mbox{\scriptsize\it Izq}}P_{\mbox......\vert P_{\mbox{\scriptsize\it Izq}}AP_{\mbox{\scriptsize\it Der}}\end{array}$La producción 6. tiene un consecuente que seinicia con una variable anterior a su antecedente. Al componer 6. con 5.obtenemos
$\begin{array}{llcl}8. & X_1 &\rightarrow& \begin{array}[t]{rr}\begin{array}[t......\vert \\ P_{\mbox{\scriptsize\it Izq}}A \\end{array}\end{array}\end{array}$Al componer 8. con 2. obtenemos
$\begin{array}{llcl}9. & X_1 &\rightarrow& \begin{array}[t]{rr}\begin{array}[t......_{\mbox{\scriptsize\it Der}}\vert \\ (A \\end{array}\end{array}\end{array}$En este momento, en nuestro conjunto actualde producciones 2., 3., 5., 7. y 9., ningún consecuente se inicia con algunavariable que anteceda a la variable en el antecedente de la produccióncorrespondiente.

 

 

 

 

 

 

 

 

 

En el paso 3. delprocedimiento para obtener formas normales de Greibach, hemos de sustituir lavariable $P_{\mbox{\scriptsize\it Izq}}$por elsímbolo (, según la producción 2., toda vez que aparezca al inicio delconsecuente de alguna producción. Obtenemos así la gramática:

\begin{eqnarray*}P_{\mbox{\scriptsize\it Izq}} &\rightarrow& ( \\P_{\mbox{\sc......mbox{\scriptsize\it Der}}\vert \\ (A \\end{array}\end{array}\end{eqnarray*}


Y esta gramática ya queda en forma normal de Greibach. Observemos que lavariable $P_{\mbox{\scriptsize\it Izq}}$esirrelevante. De hecho si hacemos la sustitución del otro símbolo $P_{\mbox{\scriptsize\it Der}}$obtenemosla gramática equivalente

\begin{eqnarray*}S &\rightarrow& ()X_1\vert(AX_1\vert()\vert(A \\A &\rightarr......\vert \\ (AX_1\vert \\ ()\vert \\ (A \\end{array}\end{array}\end{eqnarray*}


que también está en forma normal de Greibach.

MÁQUINASDE TURING

Estas son autómatas finitascon dos pilas que tienen un topecomún. O equivalentemente, son autómatas que poseen una memoria dada por una cinta la cual es un almacenamientolineal, infinito a ambos lados, con acceso a cualquier localidad en ella. Eltope común es la casilla leída (``scannedcell''), una pila es la parte de la cinta a la derecha de lacasilla leída y otra pila es su parte izquierda. Las transiciones de la máquinaquedan determinadas por una función $t : Q \times T \rightarrow Q \times T \times \mbox{\it Mov\/}$,donde $\mbox{\it Mov\/} = \{\mbox{\it Der\/},\mbox{\it Izq\/}\}$.Esta vez, la relación $t(q,a) = ( p, b, \mu )$se interpretacomo sigue: ``Si se está en el estado q y se lee el símbolo aentonces se escribe b, se pasa a p y se va a examinar la casillaal lado $\mu$de la leída''. De hecho, larelación $t(q,a) = ( p, b, \mu )$puedeescribirse como $(q,a;p,b,\mu)$, y por esto, decimosque una máquina de Turing queda especificada por su lista de quíntuplas. O, abusando aún más dellenguaje, que una lista de quíntuplas es el programacorrespondiente a una máquina de Turing.



 

 

Ejemplo:Cadenas equilibradas de paréntesis Paratener una cadena equilibrada, cada ``)'' en ella ha de ``empatar'' con uncorrespondiente ``('' que lo anteceda. Para reconocer cadenas equilibradasprocederemos como sigue:

  • Cada ``('' ya empatado se marcará como ya revisado por una A y cada ``)'' se marcará por una B.
  • Inicialmente, se busca el primer ``)'', yendo de izquierda a derecha.
  • Por cada ``)'',
    • se marca con B,
    • se busca hacia la izquierda el primer ``('' que lo empate,
    • si no se encontrare tal ``('' la cadena está desequilibrada. En otro caso, el ``('' se marca con A y se repite este ciclo.
  • Si quedaren ``('' no empatados, la cadena está desequilibrada. En otro caso se tiene equilibrio y se termina el proceso.

 


Los cuatro estados de la máquina tienen una interpretación evidente:

\begin{eqnarray*}1 &:& \mbox{\rm avanza a la derecha buscando \lq\lq )'',} \\2 &:&......odo haya sido marcado,} \\4 &:& \mbox{\rm estado terminal.}\end{eqnarray*}

 

 

 

 

 


REDUCIBILIDAD

 computables y no computables

El identificar los problemas que soncomputables y los que no lo son tiene un considerable interés, pues indica elalcance y los límites de la computabilidad, y así demuestra los límitesteóricos de los ordenadores. Además de las cuestiones sobre algoritmos, se hanencontrado numerosos problemas menos "generales" que han resultado serno computables. La mayoría de las demostraciones de no computabilidad se basanen el método de la diagonal. Como ejemplos de estos problemas podemos citar:

1.- El problema de la palabra para Grupos.-Dado un subconjunto S de elementos de un grupo G, se trata de decidir si unaexpresión compuesta por elementos de S y con las operaciones del grupo es igualal elemento neutro del grupo. Durante muchos años se buscaron ejemplos degrupos finitamente presentados para los que este problema fuese indecidible. Laexistencia de uno de estos grupos fué encontrada por Novikov en 1955 y porBoone en 1957. En el algebra moderna hay abundantes ejemplos de interesantesproblemas no computables; una gran cantidad de ellos sobre propiedades depalabras o generadores semejantes al problema de la palabra para grupos.

2.- Décimo problema de Hilbert. Una ecuacióndiofántica es la ecuación de los ceros enteros de un polinomio con coeficientesenteros. El décimo problema de Hilbert, propuesto en 1900, pregunta si hay unprocedimiento efectivo que determine si una ecuación diofántica tiene o nosolución. Y. Matiyasevich demostró en 1970 que este problema no tiene solución.

3.- Decibilidad de las teorías lógicas. Eldesarrollo de la teoría de la computabilidad ha ido íntimamente ligado aldesarrollo de la lógica matemática. Esto ha sido así porque la decibilidad delos distintos sistemas lógicos es una cuestión fundamental.

Es bastante fácil ver que el cálculoproposicional es decidible. Church y Turing demostraron en 1936 que el cálculode predicados no era decidible. Por otro lado, para cada una de las distintasteorías se ha ido estudiando su posible decibilidad. Como ejemplo másilustrativo, Tarski demostró que la teoría de los números reales era decidible.

Por otro lado, son muchos los problemasinteresantes que se han demostrado computables. Todas las funciones construidaspor recursividad primitiva o minimalización a partir de funciones calculablesresultan ser calculables como consecuencia de los trabajos de Church y Turing.Pero además, otras funciones más complejamente definidas también soncomputables, siendo el resultado más significativo en relación con estacuestión el dado por el siguiente teorema:

Primer teorema de Recursión. Todo operador entre funciones calculables que searecursivo (esto es que se defina la imagen de f mediante una función calculableen términos de una parte finita de f), tiene una función parcial computable quees el menor punto fijo, es decir, esta función es un punto fijo y cualquierotro punto fijo del operador es una extension de esa función.

 

 

Este teorema recibe su nombre porque podemosdefinir una función mediante una ecuación recursiva más general que lapermitida por la recursividad primitiva, a saber

donde es un operador recursivo. El primer teoremade recursión nos dice que esta definición es posible; hay una función recursivaque satisface esta ecuación. Como en matemáticas se requiere que la definiciónsea unívoca, se dice que dicha ecuación define el menor punto fijo del operador. Así, y de acuerdo al primer teorema derecursión, la clase de las funciones calculables es cerrada bajo una muygeneral forma de definición por recursión.

Como ejemplo más interesante de aplicaciónde este tipo de recursión tenemos la función de Ackermann :

 

 

 

 

 

A menudo se utiliza la técnica de reducir unproblema a otro para comprobar si tiene o no solución efectiva. La estratégiaen el caso de la respuesta negativa es la siguiente, si se reduce de formaefectiva un problema sin solución efectiva a otro problema (mediante unafunción calculable), entonces este nuevo problema tampoco tendrá soluciónefectiva. La razón es muy simple, si tuviese solución efectiva, componiendo el algoritmosolución con el algoritmo de transformación obtendríamos una solución para elproblema efectivamente irresoluble. En sentido inverso, si se reduce unproblema a otro para el que se conoce una solución efectiva, entoncescomponiendo se obtiene una solución para el primer problema. Esta técnica esmuy útil y se utiliza a menudo. Por otro lado, esta mísma técnica es muyempleada en el campo de la complejidad algorítmica. Para asegurarse de que unproblema está en una clase de complejidad, basta reducir el problema a otro dedicha clase sin más que asegurarse que la reducción se realiza en lacorrespondiente clase de complejidad.

 

Lenguajes aceptables y decidibles

- Lenguaje decidible: esaquel lenguaje L para el cual existe una máquina de Turing que

puede aceptar cualquiercadena w∈L y rechazar cualquier cadena w∉L.

- Lenguaje aceptable: esaquel lenguaje L para el cual no existe ninguna máquina de

Turing que puede aceptarcualquier cadena w∈L y rechazar cualquier cadena w∉L.

- Lenguajes recursivamenteenumerables: lenguajes estructurados por frases.

- Lenguajes recursivos:lenguajes decidibles por una máquina de Turing.

 

TEORIA DE LA COMPUTACION

PABLO DANIEL MALAGAPALMA

ING.SIST.COMP
SAN ANDRES TUXTLA
AUTOMATAS.

Escrito por daniel20 el 11/06/2006 02:17 | Comentarios (1)

Comentarios

no me gusta tu pajina

Escrito por sel 22/11/2009 03:36

Añadir un Comentario:



Inserta aquí el código de verificación que ves en la imagen.

Acerca de daniel20

TEORIA DE LA COMPUTACION

Archivo

Suscríbete

RSS | Atom

Contacto

Contactar

Albergado en:blogdiario.com

Noticias: Noticias