TEOREMAS

TEOREMA DE GODEL

 

 

Este era un joven llamado Kurt Gódel nació en Australia, fue un estudiante excelente, estudio y se convirtió en maestro de dicha escuela.

Godel se convirtio en famoso por su Teorema de Incompletud , ya que este fue publicado en 1931 y trata Sobre las proposiciones formalmente indecidibles en los Principia Mathematica y sistemas análogos. Este teorema demuestra que en cualquier sistema matemático, hay proposiciones que no pueden ser probadas, ni rechazadas, dentro de los axiomas del sistema. Por lo tanto Dado un conjunto de axiomas, CUALQUIERA, existirán proposiciones, que NO se podrán demostrar.

Gódel se fue interesando progresivamente en La Teoría de Números y, después, en la Lógica Matemática.

 

Godel uso un termino para discutir que una computadora nunca puede ser tan listo como un humano ya que por la extensión de su conocimiento, es limitada por un conjunto fijo de axiomas, mientras que gente puede descubrir las verdades inesperadas..

Según en el año 1 931, Godel provo que su famoso teorema da incompletud sobre la natureza da matemática afirmara que, dentro de qualquier sistema formal de axiomas, como a matemática atual, siempre persisten cuestiones que pueden ser provadas y refutadas con base los axiomas que definen o sistema.

 

TEOREMA DE GREIBACH

 

Sea C la clase de lenguajes que son efectivamente cerrados bajo concatenación con conjuntos regulares y unión, y para los cuales “=S * ” es indecidible para cualquier S fijo suficientemente grande. Sea P cualquier propiedad no trivial que es verdadera para todo conjunto regular y que se preserva bajo /a, donde a es un solo símbolo. TEOREMA. Los LLC inherentemente ambiguos son indecidibles.

 

Forma Normal de Greibach

 

Lema

“Toda gramática independiente del contexto puede reducirse a otra equivalente sin reglas recursivas a izquierdas”

Ejemplo:

A::=Ab | ACD | bDC | a |

Posible derivación desde A:

A?ACD ?AbCD?AbbCD?ACDbbCD?bDCCDbbCD

Cada derivación podría comenzar con: bDC | a y seguir con la repetición 0 o n veces de: b | CD.

La parte correspondiente a la repetición de b | CD se podría obtener con (reglas no recursivas a izquierdas):

B:= bB | CDB | b | CD y juntando con A se obtiene la parte del comienzo de las derivaciones de A:

A::=bDCB | aB | bDC | a

El conjunto de las reglas para A y B obtiene las mismas derivaciones que la gramática inicial.

 

PROBLEMAS DE CORRESPONDENCIA DE POST

 

El problema de correspondencia de post puede utilizarse para demostrar que una amplia variedad de problema de son irresolubles. Una palabra w en el lenguaje libre de contexto (LLC) es ambigua en una GLC G que genera a L si w posee mas de una derivación siniestra (leftmost) en G. como un ejemplo trivial, se tiene que, en la gramática con producciones s ? A|E

 

 

A ? ? la palabra a posee dos derivaciones siniestras

B ? ?

 

AUTÓMATAS DE PRESIÓN AUXILIARES

 

L

os PDAs, son autómatas de pilas auxiliares con entrada de dos direcciones y un almacenamiento adicional para objetivos generales, el cual se encuentra en forma de una cinta de Turing con límite espacial. La propiedad destacada de los autómatas de presión determinísticos consiste en que, para una cantidad fija de almacenamiento extra, las versiones determinística y no determinística son equivalentes en poder de reconocimiento de lenguajes, y la clase de lenguajes aceptadas por los PDAs auxiliares con un límite espacial dado es equivalente a la clase de lenguajes aceptados por las máquinas de Turing de complejidad temporal exponencial en el límite espacial.

 

Un autómata de presión auxiliar S(n) (APDA) consiste en:

 

Una cinta de entrada de sólo lectura, precedida y seguida por los señaladores de extremos ¢ y $,

Un control finito de estados,

Una cinta de almacenamiento de lectura – escritura de longitud S(n), en la que n es la longitud de la cadena de entrada w, y

Una pila.

 

Un autómata de presión auxiliar se esquematiza de la siguiente manera:

 

 

Equivalencia de los APDAs determinísticos y no determinísticos.

 

El interés que se tiene en los APDAs se originó a partir del descubrimiento de que los APDAs determinísticos con el mismo límite espacial son equivalentes, y de que un espacio S(n) sobre un APDA es equivalente a un tiempo c S(n) sobre una máquina de Turing. Esto es, las siguientes tres proposiciones son equivalentes.

 

L es aceptado por un APDA determinístico con límite espacial S(n).

L es aceptado por un APDA no determinístico con límite espacial S(n).

L se encuentran en TIEMPOD(c S(n) ), para alguna constante c.

 

Lema 1. - L es aceptado por un APDA determinístico con límite espacial S(n), A, en el que S(n) = log n, entonces L se encuentra en TIEMPOD(c S(n) ), para alguna constante c.

 

Demostración: Hagamos que A tenga s estados, t símbolos de almacenamiento y p símbolos de pila. Dada una entrada de longitud n, existen n + 2 posiciones de la cabeza de entrada, s estados, S(n) posiciones de la cabeza de almacenamiento y t S(n) contenidos de la cinta de almacenamiento posibles, para hacer un total de:

 

s(n) =(n + 2)sS(n)t S(n)

 

configuraciones posibles.

 

Demostración: L es aceptado por una TM de una cinta y límite temporal ½ T 2 (n), M 1 . Cuando M 1 se mueve en la dirección opuesta, M abandona al señalador de cabeza, completa su barrido y simula ese movimiento en el recorrido de regreso. Por consiguiente M simula al menos un movimiento de M 1 por recorrido, tomando un máximo de S ½T2(n) n + i = T 4 (n) movimientos para completar la simulación de M 1 .

 

Lema 3. – Si L se encuentran en TIEMPOD(c S(n) ), para alguna constante c, entonces L es aceptado por un APDA determinístico con límite espacial S(n).

Nótese que como el movimiento de la cabeza de M es independiente de los datos, la celda barrida al tiempo t se puede calcular de manera sencilla a partir de t.

 

Lema de bombeo:

 

El lema de bombeo dice básicamente lo siguiente:

 

Si un lenguaje infinito es regular, este puede ser definido por un autómata finito.

El autómata tiene un número finito de estados. (digamos, p)

Como el lenguaje es infinito, algunas cadenas en el lenguaje pasarán más de una vez por algún estado. (estas serán las cadenas que tengan un largo mayor que el número de estados del autómata).

Al repetir el ciclo cuantas veces queramos, el generaremos cadenas que también están en el lenguaje.

 

Definición formal:

 

Si L es un lenguaje regular definido sobre S, entonces existe una constante n natural y positiva, tal que, cualquier palabra z ? L , con _ | z| > n , siempre puede escribirse como z = uvw , con u , v, w ? ?*

 

 

Además, n < | Q| , siendo Q el conjunto de estados del AFD mínimo que reconoce L .

 

 

 

MINIMIZACIÓN DE AUTÓMATAS FINITOS

 

Sea $\mbox{\it Ent\/}$un alfabeto finito. Según vimos anteriormente la noción de lenguaje regular puede presentarse mediante el reconocimiento por autómatas finitos, sean deterministas o no, o mediante la representación por expresiones regulares. Otras presentaciones equivalentes de esta noción se dan en la siguiente:

Proposición : ( Teorema de Myhill-Nerode)   Sea $L\subset\mbox{\it Ent\/}^*$un lenguaje arbitrario. Las siguientes aseveraciones son equivalentes a pares:

 

L es regular.

  1. L es la unión de algunas clases de equivalencia de una relación de equivalencia de índice finito, congruente por la derecha con la concatenación de palabras.

 

La relación $\equiv_L\subset\left(\mbox{\it Ent\/}^*\right)^2$tal que L = l (AF) es una relación de índice finito

 

 

 

FORMA NORMAL DE CHOMSKY

 

Una gramática independiente del contexto se encuentra en forma normal de Chomsky si el lado derecho de cada una de sus reglas está constituido por un único símbolo terminal o por dos no terminales.

 

Teorema:

Si L es un lenguaje independiente del contexto sin la palabra vacía, existe una gramática

en forma normal de Chomsky que genera dicho lenguaje.

 

El teorema nos permite mostrar que una propiedad es irresoluble mediante la demostración de que la propiedad se conserva con respecto al cociente con un solo símbolo. Esta última tarea es, con frecuencia, relatividad sencilla como, por ejemplo, cuando se demuestra que la ambigüedad inherente es irresponsable

 

Demostración:

Sea la gramática G (V, S, S, R), que no contiene reglas ?. Se realiza sobre ella el siguiente proceso:

Para cada símbolo terminal x se introduce la regla X ? x , donde X es un símbolo no terminal nuevo que no pertenecía a V, y se sustituye x por X en todas las demás reglas de G.

Cada regla de la forma N ? N 1 Nn -2... Rn -2 ? Nn -1 Nn , donde los Ri son símbolos no terminales nuevos que no pertenecían a V. Al llegar a este punto, la gramática contiene sólo reglas que en la parte derecha tienen un único terminal, dos no terminales o un único no terminal. Estas últimas reglas se pueden eliminar efectuando el siguiente paso:

Para cada secuencia de reglas Nn ? Nn -1, Nn -1 ? Nn -2,..., N 2 ? N 1 se añade la regla Nn ? x si N 1 ? x estaba en G, y Nn ? AB si N 1 ? AB estaba en G, y se eliminan entonces las reglas que tienen un único no terminal en su parte derecha.

 

Si el lenguaje contiene la palabra vacía, se añade un nuevo símbolo S', que será el inicial, con una regla S' ? ?, y para cada regla S ? w en G, siendo w un terminal o dos no terminales, se añade la regla S' ? w .

 

 

Teoría de la Computabilidad

 

La teoría de la computabilidad, también denominada teoría de la recursión, es una de las cuatro partes que constituyen la lógica matemática, siendo las otras tres, la teoría de conjuntos, la teoría de modelos y la teoría de la demostración y se ocupa del estudio y clasificación de las relaciones y funciones computables. Además, la teoría de la computabilidad, junto con la teoría de autómatas, lenguajes y máquinas, es el fundamento de la informática teórica y esta, a su vez, de la industria de los ordenadores.

 

 

TESIS DE CHURCH : Toda función para la cual exista un proceso algorítmico que pueda ser especificado mediante la descripción a alto nivel de una serie de pasos a realizar, es computable. Cuando esto ocurre, podemos asegurar la computabilidad de f en virtud de la tesis de Church, sin necesidad de calcular un programa específico para f.

Computabilidad-Turing

Una función $I\!\!N^n\rightarrow I\!\!N$se dice ser computable- T , o computable-Turing , si existe una máquina de Turing que la calcula. Antes que nada, consideraremos en esta sección que los números naturales se están representando en base 2, utilizando únicamente a los dígitos 0,1.

 

Este módulo presenta los conceptos relativos al tema de Complejidad Computacional, como son el concepto de complejidad temporal y orden de un algoritmo. También se describen las diferentes clases de problemas de decisión y su correspondencia con los problemas de optimización.

Finalmente, se describen los diversos enfoques tomados para su solución, como son resolución y búsqueda local.

Tipos de complejidad:

La complejidad temporal tiene que ver con el tiempo que tarda un programa para ejecutarse. La complejidad espacial estudia la cantidad de espacio de almacenamiento que es necesario para una operación. La gran mayoría de estudios de complejidad están orientados hacia el desempeño de los algoritmos en función al tiempo, por lo que de aquí en adelante, al hablar de complejidad, se asumirá que es en el tiempo.

 

Tesis de Church-Turing

 

Tesis de Church: "(Church-Turing) A function of positive integers is effectively calculable only if recursive."Versión de la Tesis de Church-Turing más utilizada: Todo algoritmo o procedimiento efectivo es Turing-computable.

Aunque el problema queda trasladado de "algoritmo" o "procedimiento efectivo" a "computable".

 

EL PROBLEMA CIRCUITAL DE HAMILTON

 

El problema circuital de Hamilton es: Dado un grafo, ¿ tiene G una trayectoria que toca a cada vértice exactamente una vez y regresa a su punto inicial ? El problema circuital de Hamilton dirigido es el problema análogo para los grafos dirigidos. Representamos estos problemas como lenguajes Lh y Ldh codificando los grafos de la misma forma que en el problema de cobertura de vértices.

Teorema: Ldh , el problema circuital de Hamilton dirigido, es NP-completo.

 

GRAFO CONCERNIENTE A LOS CIRCUITOS DE HAMILTON DIRIGIDOS

 

Problemas de programación lineal entera

 

Un problema es de programación lineal entera, cuando prescindiendo de las condiciones de integridad, el problema resultante es un problema de programación lineal.

CLASIFICACION DE LOS PROBLEMAS LINEALES ENTEROS

Atendiendo al tipo de variables:

 

Enteros puros.

Mixtos

Binarios

 

Atendiendo al criterio del tipo de problema

 

Directo

Codificado

Transformado

 

Métodos de resolución

 

METODO DE RAMIFICACION Y ACOTACION.La ramificacion consiste en dividir cada problema de dos nuevos subproblemas, obtenidos mediante la imposicion de restricciones excluyentes que dividen el conjunto de oportunidades del problema original en dos partes, pero eliminando Ambas partes la solucion no entera del problema original Utilizando únicamente la ramificación, el numero de subproblemas a resolver crece exponencialmente por este motivo para evitar el tener que resolver todos los subproblemas, la ramificación se combina con la acotación. La acotación se basa en el hecho de que dado que los conjuntos de oportunidades de un subproblema y otro pertenecientes a su vez como subconjuntos del conjunto de oportunidades de un problema primario, la solución optima de los dos subproblemas siempre será inferior que la solución optima de problema primario por ser los conjuntos de elección menores.

 

Formas normales

 

Forma Normal de Chomsky. Forma de una gramática independiente del contexto que se caracteriza mediante reglas de reeescritura cuyo lado derecho consiste en un solo símbolo terminal o exactamente dos no terminales.

 

Forma Normal de Greibach. Toda GIC G se puede transformar en una nueva GIC G'

equivalente a G, expresada en Forma Normal de Greibach

(FNG). Pierre de Fermat

 

Pierre de Fermat, que nació en el año 1601 en Beaumont-de-Lomagne, Francia, y murió en París en 1665, fué de profesión jurista y aficionado a la Matemática, disciplina en la que dejó resultados notables tanto en teoría de curvas, como en el cálculo de probabilidades o en la teoría de números.

 

La Última conjetura de Fermat, o bien, como generalmente ha sido denominada, El último Teorema de Fermat, afirma sencillamente que la expresión no tiene solución para n > 2. O sea, que si x n e y n son potencias perfectas de números enteros, nunca podrá ser x n + y n potencia perfecta de números enteros cuando es n > 2.

 

TEOREMA DE RICE

 

Consideremos la clase de funciones recursivas con un solo argumento. Sea pues $\mbox{\it FRec}^1=\left\{f_k\right\}_{k\geq 0}$una enumeración efectiva de las funciones computables de una sola variable. El conjunto de índices de ${\cal F}$es $R_{{\cal F}}=\{i\geq 0\vert f_i\in {\cal F}\}.$La clase ${\cal F}$se dice ser recursiva si su conjunto de índices $R_{{\cal F}}$lo es, es decir, si la función característica de este último conjunto es recursiva.

 

Teorema 1.1 (Rice)  

Ninguna subclase propia no vacía de funciones recursivas ${\cal F}\subset\mbox{\it FRec}^1$puede ser recursiva. En otras palabras, si existen $f,g\in\mbox{\it FRec}^1$tales que $f\in{\cal F}$y $g\not\in{\cal F}$entonces ${\cal F}$no puede ser recursiva.

 

Demostración: Supongamos que ${\cal F}$sea recursiva y que existen $f,g\in\mbox{\it FRec}^1$tales que $f\in{\cal F}$y $g\not\in{\cal F}$.

Existe pues una función recursiva $P_{{\cal F}}\in \mbox{\it FRec}^1$que coincide con la función característica de $R_{{\cal F}}$, es decir, tal que

\begin{displaymath}P_{{\cal F}}(i)=\left\{\begin{array}{ll} 1 &\mbox{\rm si $i\... ... F}}$, } \\ 0 &\mbox{\rm en otro caso. } \end{array}\right.\end{displaymath}

Definamos de manera que \begin{displaymath}h(i,x)=\left\{\begin{array}{ll} g(x) &\mbox{\rm si $i\in R_{... ...}$, } \\ f(x) &\mbox{\rm en otro caso. } \end{array}\right.\end{displaymath}

 

h es recursiva pues se está definiendo por casos utilizando funciones recursivas.

 

Por el Teorema de Parametrización, existe una función recursiva tal que $\forall i,x:\ f_{s(i)}(x)=h(i,x).$Por el Teorema de Recursión ha de existir un k 0 tal que f k 0 = f s ( k 0) .


Digamos que una clase de funciones es trivial si bien es vacía, o bien coincide con toda la clase. El Teorema de Rice asevera pues que las únicas clases de funciones que son recursivas son precisamente las triviales.

 

Teorema 1.2 (Rice: Versión vectorial)

Sea ${\cal F}^m\subset\left(\mbox{\it FRec}^1\right)^m$una familia de m -tuplas cuyas componentes son funciones recursivas.

Sea $R_{{\cal F}^m}=\left\{(i_1,\ldots,i_m)\vert(f_{i_1},\ldots,f_{i_m})\in {\cal F}^m\right\}.$Entonces $R_{{\cal F}^m}$no puede ser recursivo a menos de que $R_{{\cal F}^m}$sea trivial, es decir, $R_{{\cal F}^m}=\emptyset$o $R_{{\cal F}^m}=I\!\!N^m$

Demostración: Sea $a_m:I\!\!N^m\rightarrow I\!\!N$una bisección computable. Del Teorema de Rice se sigue que S no es recursivo.

Teorema 1.3 (Primera extensión del Teorema de Rice)

Sea ${\cal F}\subset\mbox{\it FRec}^1$una familia de funciones recursivas tal que existe una función $f\in{\cal F}$con una extensión propia recursiva g que NO está en ${\cal F}$. Entonces el conjunto de índices $R_{{\cal F}}=\{i\geq 0\vert f_i\in {\cal F}\}$no puede ser recursivamente enumerable.

 

 

Demostración: Sean f y g como en el enunciado del teorema. Sea $\left(f_i\right)_i$una enumeración efectiva de las funciones recursivas.

Consideremos la función tal que \begin{displaymath}h(i,x)=\left\{\begin{array}{ll} f(x) &\mbox{\rm si $f_i(i)\u... ...w$, } \\ g(x) &\mbox{\rm en otro caso. } \end{array}\right.\end{displaymath}. La función es claramente computable, pues es la diagonal de una función universal. Como f y g son recursivas, existen sendos programas Q 1 , Q 2 que las calculan. Por el Teorema de Parametrización existe una función computable s tal que $\forall i,x:\ f_{s(i)}(x)=h(i,x).$Así pues, $\forall i:[s(i)\in R_{{\cal F}}\Leftrightarrow f_i(i)\uparrow]$.

 

Ahora bien, el conjunto $K=\{i\vert f_i(i)\downarrow\}$bien que es recursivamente enumerable no es recursivo (éste aparece de manera esencial en el Problema de la Parada).

 

 

Lema de Bombeo para GLC's: Sea L un LLC . Existe una constante $n\in I\!\!N$tal que si $\mbox{\bf z}\in L$es una palabra de longitud al menos n entonces la palabra $\mbox{\bf z}$se puede descomponer como $\mbox{\bf z}=\mbox{\bf z}_1\mbox{\bf z}_2\mbox{\bf z}_3\mbox{\bf z}_4\mbox{\bf z}_5$, de manera que $\mbox{\rm long}(\mbox{\bf z}_2)+\mbox{\rm long}(\mbox{\bf z}_4)\geq 1$, $\mbox{\rm long}(\mbox{\bf z}_2\mbox{\bf z}_3\mbox{\bf z}_4)\leq n$, y $\forall k\in I\!\!N:\ \mbox{\bf z}_1\mbox{\bf z}_2^k\mbox{\bf z}_3\mbox{\bf z}_4^k\mbox{\bf z}_5 \in L$.

Ahora bien toda máquina de Turing es equivalente, mediante la adición de estados redundantes, a una máquina de Turing tal que toda computación terminal involucra al menos tres DI's. De aquí se tiene el

 

Lema 3.1   Sea M una máquina de Turing. Sea C M el conjunto de computaciones terminales en M . Entonces \begin{displaymath}C_M\mbox{\rm es un LLC }\ \Leftrightarrow\ L(M)\mbox{\rm es un lenguaje finito.}\end{displaymath}

Demostración: Si L ( M ) fuera infinito y C M libre de contexto se contradiría al Lema de Bombeo. $\Leftarrow)$Es evidente, pues todo lenguaje finito es libre de contexto. Para m =2 y a =100 tenemos a =1100100 2 =2 6 +2 5 +2 2 ,

luego

\begin{displaymath}\mbox{\it rp}_2(100)=2^{2^2+2} + 2^{2^2+1} +2^2.\end{displaymath}

Escribamos Con esta notación denotaremos por al resultado de sustituir a m por k .

 

LENGUAJES INDEXADOS

Una gramatica indexada es un conjunto de cinco parametros (V, T, I, P ,S) en el que V es el conjunto de variables , T es el conjunto de terminales, I el conjunto de índices, S en V el símbolo inicial y P el conjunto finito de producciones de las formas.

1. LA ? a, 2. A ? Bf o 3. Af ? a,

En las que A y B se encuentran en V, F en I y a en (V ? T)*

Las derivaciones de una gramatica indexada son parecidas a la de una CFG, excepto que las variables pueden estar seguidas de cadenas de índices. (Las terminales pueden no estar seguidas por índices). Cuando se aplica una producción como A ? BC, la cadena de índices para A se asigna a B y C. Esta característica permite que muchas partes de una forma oracional sean relacionadas entre sí mediante el comportamiento de una cadena de índices común.

Teorema de la complejidad Axiomática

 

Las primeras noticias en contra surgen en 1931 con Kurt Gödel (1906-1978) y su Teorema de Incompletitud [1931]: “Todo sistema de primer orden consistente que contenga los teoremas de la aritmética y cuyo conjunto de axiomas sea recursivo no es completo".

 

Kurt Gödel, 1931, presenta su famoso teorema de la incompletitud de Gödel , el cual viene a decir que: “toda formulación axiomática consistente en la teoría de números contiene proposiciones indecidibles". Teoría de Autómatas y Lenguajes Formales

 

Teorema de Unión

 

Otro fenómeno curioso con respecto a las medidas de complejidad es el que se refiere a que existen funciones que no tienen mejores programas (maquina de Turing). Ya hemos visto que cada TM permite una aceleración lineal en el tiempo y una compresión lineal en el espacio.

 

El último teorema de asta sección, conocido como teorema de unión, tiene que ver con la asignación de los nombres de las clases de complejidad.


Teorema Sea {f i (n) | = 1,2, ...} una colección recursivamente enumerable de función recursivas. Entonces existe una S(n) recursiva tal que

ESPACIOD(S(n)) = ¡å ESPACIOD(fi (n)).

 

 

TEOREMA DE PDAs

 

Teorema.: Para cualquier idioma regular hay un DPDA que lo acepta.

 

Prueba.

 

Una máquina estatal finita simplemente es un PDA que no hace uso de su pila. Dado un idioma regular nosotros podemos crear un DPDA para aceptarlo como sigue: Primero cree un DFA para el idioma regular, entonces cambie su transición etiqueta para que en lugar de simplemente un carácter de la entrada, cada transición se etiquete con un carácter de la entrada y dos lambdas en lugar del estallido y caracteres del empujón. QED

EJEMPLO

 

Diseñar un AFPD que acepte el lenguaje { a i b i : i > 1 } , sobre el alfabeto = { a, b }

 

Copiar las a en la pila y borrar una a por cada b que sea leida sobre la cinta. Una palabra será aceptada si es procesada completamente y en la pila sólo queda el símbolo s 0 .

 

(q 0 , aaabbb, s 0 ) ? (q 0 , aabbb, As 0 ) ? (q0, abbb, AAs 0 ) ? (q0, bbb, AAAs 0 )

? (q1, bb, AAs 0 ) ? (q1, b, As 0 ) ? (q1, ?, s 0 ) ? (q2, ?, s 0 )

 

La última es una configuración de aceptación; por lo tanto aaabbb es aceptada.

Para la palabra de entrada w = aabbb, se obtiene el siguiente procesamiento:

 

(q 0 , aabbb, s 0 ) ? (q 0 , abbb, As0) ? (q0, bbb, AAs0) ? (q1, bb, As0) ? ` (q1, b, s0) ? [computo abortado]

 

Para la palabra de entrada w = aaabb, se tiene:

 

(q0, aaabb, s0) ? (q0, aabb, As0) ? (q0, abb, AAs0) ? (q0, bb, AAAs0) ? (q1, b, AAs0) ? (q1, _, As0)

 

A pesar de que se ha procesado completamente la palabra de entrada, la configuración (q0, ? , As0) no es de aceptación.

 

Teorema: Para s(n) = log n, las siguientes proposiciones son equivalentes:

L es aceptado por un APDA determinístico con límite S(n).

L es aceptado por un APDA no determinístico con límite S(n).

Corolario: L se encuentra en P si y sólo si L es aceptado por un APDA con límite espacial log n.

 

EJEMPLO

 

La parte medular de la construcción de un APDA determinístico con límite S(n), A, que acepte a L consiste en el procedimiento recursivo PRUEBA, que asigna el valor de verdadero a (q, Z, t) si y sólo si.

 

t=0, q es el estado inicial y Z el símbolo de la primera celda de M,

al tiempo t, M barre por primera vez una celda, Z es el símbolo original en esa celda de cinta, y existe un triplete (p, X, t - 1) que es verdadero e implica que M accesa el estado q después de un movimiento, o

M ha barrido, previamente, la celda visitada en el tiempo t y existen tripletes verdaderos (p 1 , X 1 , t - 1) y (p 2 , X 2 , t') tales que el primer triplete implica que q es accesado después de un movimiento, y el segundo implica que Z se quedo en la celda de cinta la última vez que ésta fue barrida. Recuérdese que el movimiento de la cabeza M es uniforme y, por tanto, el tiempo t ' , al cual la celda fue visitada por última vez, se puede calcular fácilmente a partir de t.

 

Procedimiento recursivo PRUEBA:

 

procedure PRUEBA (q, Z, t);

begin

if t=0, que es el estado inicial de M y Z es el primer símbolo de entrada then return true;

if 1= t <n y Z es el t-ésimo símbolo de entrada, o t= in + i (i- 1)/2, para algún entero i = 1, y Z = B, then

for cada estado p y símbolo X do

if M entra el estado q cuando esta barriendo a X en el estado p, y PRUEBA (p, X, t – 1)

then return true;

/* los tiempos in + i (i- 1)/2 son exactamente los tiempos en que M barre una nueva celda */

if t = n y t ? in + i (i- 1)/2, para cualquier entero i = 1 then

begin

sea t ' la ocasión anterior en que M barrió la misma celda que en el tiempo t;

for todos los estados p 1 y p 2 y los símbolos X 1 y X 2 do

if M entra un estado q cuando está barriendo a X 1 en el estado p 1 y M escribe Z cuando barre a X 2 en el estado p 2 y Prueba (p 1 , X 1 , t -1) y PRUEBA (p 2 , X 2 , t')

then return true

end;

return false

end

 

Dado que PRUEBA solamente se llama a sí misma con argumentos menores, finalmente termina. El APDA es espacio S(n), A, evalúa a PRUEBA manteniendo los argumentos en la cinta de almacenamiento.

 

El algoritmo completo que A ejecuta es:

 

for cada triplete (q, Z, t) tal que q es un estado de aceptación y 0=t = d S(N) do

if PRUEBA (q, Z, t) then accept

 

El último Teorema de Fermat.

 

Afirma sencillamente que la expresión no tiene solución para n > 2. O sea, que si x n e y n son potencias perfectas de números enteros, nunca podrá ser x n + y n potencia perfecta de números enteros cuando es n > 2.

Si dividimos por z2 toda la ecuación, se tendría:

 

Que es, evidentemente, la ecuación de una circunferencia de radio unidad.

 

Partamos de la solución particular más simple. Por ejemplo de A = 1, B = 0. También serán soluciones A= -1, B = 0, y A = 0, B = 1, o, también, A= 0, B = -1. Estas soluciones, las más simples por ser enteras, estarían situadas en los puntos de corte de la circunferencia de radio unidad con los ejes cartesianos del plano AB:

 

Sobre la conjetura de Fermat Todos los puntos de esa circunferencia verifican, evidentemente, la ecuación de la misma, es decir, están sobre la circunferencia, por lo que la intersección de una recta cualquiera con la circunferencia nos dará un punto solución de la ecuación anterior..

Sin embargo, los casos no pitagóricos N > 2 no admitían ni un solo ejemplo de existencia de solución entera, ni tampoco se le pudo encontrar una prueba de imposibilidad de soluciones durante más de 350 años.

 

Durante estos años hubo muchos intentos de demostración de la conjetura de Fermat.

 

 

TEOREMA DE MYHILL NERODE

El teorema de Myhill-Nerode dice que las siguientes afirmaciones son equivalentes.

(1) L es aceptado por un autómata finito.

(2) L es la unión de algunas de las clases de equivalencia de una relación RM de índice finito.

(3) Si una relación de equivalencia RL esta definida por

 

 

Entonces el numero de clases de equivalencia de RL (índice de RL) es finito.

La demostración del teorema tiene que ver con la relación RM que ya hemos definido.

(2) à (3) En efecto, RL tiene índice finito puesto que

 

Es decir, cada clase de equivalencia de RM esta contenida en una de RL.

(3) à (1) Queda como ejercicio.

La idea es construir un AFD a partir de RL que acepte L.

Teoremas de jerarquía

 

Veremos algunas condiciones suficientes para distinguir niveles de complejidad en las jerarquías deterministas espacial y temporal, compararemos algunos niveles de ellas y posteriormente veremos propiedades de las jerarquías no-deterministas. Finalmente, con el teorema de Borodin veremos que se puede tener dos funciones muy diversas que determinan, sin embargo, un mismo nivel en la jerarquía determinista espacial.

 

Jerarquía en espacio

Una función s se dice ser constructible en espacio si $\exists M\in {\cal C}$tal que

\begin{displaymath}\begin{array}{lcl} \mbox{\rm i) } t_M\asymp s &\mbox{\rm y }... ...ox{\bf x})\&\mbox{\it espa}_{M}(\mbox{\bf x})=s(n) \end{array}\end{displaymath}


El siguiente teorema determina diferentes niveles de complejidad espacial.

Teorema 4.1   Sean s 1 y s 2 dos funciones constructibles en espacio, ambas mayores que log.

 

Demostración: Construiremos una máquina M tal que $M\in\mbox{\rm DSPACE}(s_2)- \mbox{\rm DSPACE}(s_1).$Para una entrada $\mbox{\bf x}$con $n=\mbox{\it long}(\mbox{\bf x})$, M funciona como sigue:

1.

M marca s 2 ( n ) casillas.

2.

Calcula i tal que $\mbox{\bf x}=\mbox{\bf x}_i$y la máquina M i .

3.

M reconoce a $\mbox{\bf x}$si

M i ocupa espacio s 1 ,

M realiza la simulación de M i sobre $\mbox{\bf x}_i$en espacio s 2 ( n ), y

M i NO acepta a $\mbox{\bf x}_i$. En efecto, si acaso $M\in\mbox{\rm DSPACE}(s_1)$, entonces $\exists n:\; M=M_n\in\mbox{\rm DSPACE}(s_1).$De hecho, existiría una sucesión creciente de índices $\left(\phi(n)\right)_n$tal que $M_{\phi(n)}\in \mbox{\rm DSPACE}(s_1)$es equivalente a M . Ya que ${\displaystyle \liminf_{n\rightarrow +\infty}\frac{s_1(n)}{s_2(n)}=0,}$se tiene que para cualquier constante positiva c , $\exists m:\;n>m\Rightarrow c\vert s_1(n)\vert < \vert s_2(n)\vert.$Así pues, para n suficientemente grande M podría simular en espacio s 2 a $M_{\phi(n)}$a partir de la entrada inicial $\mbox{\bf x}_{\phi(n)}$. En estas condiciones se tendría $\forall n: \; (M \mbox{\rm reconoce a }\mbox{\bf x}_{\phi(n)}\;\Leftrightarrow\; M_{\phi(n)} \mbox{\rm reconoce a }\mbox{\bf x}_{\phi(n)}),$lo cual está en contradicción con la definición de M . q.e.d.

 

Jerarquía en tiempo

Una función t se dice ser constructible en tiempo si $\exists M\in {\cal C}$tal que

\begin{displaymath}\begin{array}{lcl} \mbox{\rm i) } t_M\asymp t &\mbox{\rm y }... ...ox{\bf x})\&\mbox{\it tiem}_{M}(\mbox{\bf x})=t(n) \end{array}\end{displaymath}


El siguiente teorema determina diferentes niveles de complejidad temporal.

Teorema 5.1   Sean t 1 y t 2 dos funciones constructibles en tiempo.

 

Demostración: La demostración es similar al caso espacial. La condición de límite es más fuerte debido al siguiente

Lema 5.1   Si M es una máquina de Turing de varias cintas y función de tiempo t entonces existe una máquina de Turing M 1 equivalente a ella con tan sólo dos cintas y función de tiempo $t_1=t\log t.$

Construiremos una máquina M tal que $M\in\mbox{\rm DTIME}(t_2)- \mbox{\rm DTIME}(t_1).$Para una entrada $\mbox{\bf x}$con $n=\mbox{\it long}(\mbox{\bf x})$, M funciona como sigue:

1.

En todo momento M corre ``en paralelo'' con una máquina que construye en tiempo a t 2 .

2.

Calcula i tal que $\mbox{\bf x}=\mbox{\bf x}_i$y la máquina M i .

3.

M reconoce a $\mbox{\bf x}$si

M i corre en tiempo t 1 ,

M realiza la simulación de M i sobre $\mbox{\bf x}_i$en tiempo t 2 ( n ), y

•  M i NO acepta a $\mbox{\bf x}_i$.

Teorema de Aceleración de Blum

 

Teorema (Teorema de Aceleración de Blum) Sea r(n) cualquier función totalmente recursiva. Existe un lenguaje recursivo L, tal que, para cualquier maquina de Turing Mi que acepta a L, existe una maquina de Turíng Mj que acepta aL y tal que r (Sj (n)) < = Si (n) para casi toda n.

 

ALONZO CHURCH

(14 de junio de 1903 - 11 de agosto de 1995), matemático y lógico Norteamericano responsable por crear la bases de la computación teórica. Nacido en la cuidad de Washington, se diplomó en la Universidad de Princeton en 1924 y obtuvo su doctorado en 1927, donde ejerció como profesor entre 1929 y 1967.

Su obra más conocida es el desarrollo del cálculo lambda, y su trabajo de 1936 que muestra la existencia de problemas indecidibles. Este trabajo precedió el famoso trabajo de su alumno Alan Turing sobre el problema de parada que también demostró la existencia de problemas irresolubles por dispositivos mecánicos. Luego de revisar la tesis doctoral de Turing, demostraron que el cálculo lambda y la máquina de Turing utilizada para expresar el problema de parada tenían igual poder de expresión; posteriormente demostraron que una variedad de procesos mecánicos alternos para realizar cálculos tenían poder de cómputo equivalente. Como resultado se postuló la Tesis de Church-Turing.