Buenos recursos para aprender acerca de los modelos de cálculo?

Question

Por curiosidad, estoy tratando de identificar qué modelo de cálculo de un sistema de trabajo con es funcionalmente equivalente a, y demostrar la equivalencia. Cuanto más tiempo que paso en este problema más que sospecho que el sistema no es Turing-equivalentes. Mi comprensión de las máquinas de Turing y lenguajes recursivamente enumerables es bueno, pero no sé mucho acerca de autómatas con capacidades menores (por ejemplo de pila de autómatas), así que no estoy seguro de cómo proceder.

En primer lugar, ¿alguien puede recomendar un buen recurso para aprender sobre los diferentes modelos de computación? Estoy interesado en gramáticas, autómatas y lenguajes, y la forma de demostrar la equivalencia y la diferencia entre todos ellos. Lo ideal sería que el recurso se rompería todos los elementos de cada modelo con gran detalle y compararlas.

En segundo lugar, ¿existe un enfoque general o marco que se debe utilizar cuando se trata de instalar un sistema en cualquiera de estos modelos computacionales?

Answer 1

Me gustaría recomendar un buen libro de texto sobre la informática (En mi Uni supuesto, estoy estudiando desde Introducción de Sipser a la Teoría de la computación , que es muy bueno en mi opinión. Usted puede también encontrar un libro de texto libre que enseña lo mismo, pero no tengo ninguna experiencia con uno así que no puedo recomendar).

El otro enfoque sería probablemente sólo para leer en la Wikipedia. En realidad se puede obtener una gran cantidad de kilometraje de los artículos de Wikipedia, si sabes lo que estás buscando y en qué orden. Además, si algo no está claro, por lo general puede Google y encontrar más recursos sobre este tema en particular.

Por supuesto, esto no será tan bueno como un libro de texto real, pero es un buen lugar para empezar ahora , y es gratis.

Como punto de partida, me gustaría recomendar la lectura sobre los temas siguientes (en el orden indicado):

1. determinista Autómata Finito
2. no determinista Autómata Finito , y su equivalencia con los DFA.
3. Regular Idiomas , y su equivalencia con los DFA.
4. Pushdown Autómatas
5. contexto libre gramáticas , y su equivalencia con Pushdown Autómatas.
6. jerarquía de Chomsky
7. Máquinas de Turing

Esto debería proporcionar una breve introducción a la mayoría de los modelos computacionales gente habla.    2 : Me gustaría recomendar un buen libro de texto sobre la informática (En mi curso de Uni, I' m estudio de Introducción de Sipser a la Teoría de la computación , que es muy bueno en mi opinión). El otro enfoque sería probablemente sólo para leer en la Wikipedia. En realidad se puede obtener una gran cantidad de kilometraje de los artículos de Wikipedia, si sabes lo que estás buscando y en qué orden. Además, si algo no está claro, por lo general puede Google y encontrar más recursos sobre este tema en particular. Como punto de partida, me gustaría recomendar la lectura sobre los temas siguientes (en el orden): 1. 1 : http://www.amazon.com/Introduction -Teoría-Computación-Segunda-Michael / dp / 0534950973 / ref = sr_1_1? es decir, = UTF-8 y s = libros & qid = 1263282346 y sr = 8-1

Answer 2

Las conferencias de vídeo desde el siguiente enlace da una buena introducción a la teoría de la computación. Este es uno de los mejores recursos sobre este tema.

video conferencias sobre Teoría de la Computación por el profesor Shai Simonson

Answer 3

Un texto más antiguo que puede ser difícil de encontrar es Hopcroft y "Introducción a la Teoría de Autómatas, Lenguajes y Computación" de Ullman. Hay un número de ediciones --- He oído que el 79 es la mejor, en la medida en que tira de los golpes menor cantidad en la introducción de cosas complejas. Es legítimo, aunque pequeño libro de texto, y se introduce todo el campo, no sólo lo que está buscando. Sugiero esto en la vana esperanza probable que tal vez una de esas pruebas "más difíciles" otras fuentes de dejar de lado puede ser la clave.

Como punto de partida más suave, hay algunas lenguas mano "de referencia".

• Si el modelo de puede reconocer el idioma de todas las cadenas en las que hay el mismo número de A y B en una cadena, entonces es al menos más potente que el FSM.
• Si no puede, entonces puede es equivalente a FSM.
• Del mismo modo, si el modelo de puede reconocer el lenguaje de todas las cadenas donde el son el mismo número de As, B, y C en una cadena, entonces es más poderoso que una CFG, o PDA.

Estos "lenguas de referencia" en realidad sólo son funciones disfrazados --- la primera es básicamente preguntando si 2 números unarios son iguales, el segundo está preguntando si 3 números unarios son iguales. Son agradable y simple, y son bien conocidos por estar por encima o por debajo de las capacidades de los modelos particulares. No sé simples para las máquinas más complejas, por lo que puede ser por su cuenta.

Tenga en cuenta que para el modelo "LBA", autómatas linealmente acotado, creo que no hay un lenguaje natural conocido que es computable con una TM, pero no un LBA. Esta declaración se extrae de recuerdos nebulosos, así que no lo tome como una prueba formal. :)

Nota (por último) que las lenguas "de referencia" no va a establecer la igualdad. Es decir, si el modelo no se puede comparar 2 números unarios, que hace no quiere decir que sea necesariamente equivalente a un FSM, podría ser aún más débil. Los idiomas sólo se establecen lo que es mayor que en el poder, o menor que en el poder.

En una pista por completo (por completo) diferente, el libro de Sipser Qué hace pruebas de equivalencia entre expresiones regulares y FSM, así como entre PDAs y CFGs. No estoy seguro de lo útil que será, ya que son bastante vaga de qué tipo de modelo de computación que está considerando, pero si está muerto establecer la equivalencia, los pueden ser buenos puntos de partida.