¿Por qué una máquina de Turing reconoce exactamente un idioma?

13

Estoy tratando de entender la existencia de lenguajes no reconocibles. Para obtener esto, necesito saber por qué una máquina Turing reconoce solo un idioma, no varios. ¿Por qué es esto?

Anónimo
fuente
12
Sospecho que es posible que no tenga una idea clara de lo que queremos decir con "idioma". ¿Puedes decir qué crees que es un "idioma"?
Eric Lippert
¿Por qué necesitas saber eso? ¿De qué manera crees que podría hacer la diferencia?
babou

Respuestas:

29

El lenguaje reconocido por una máquina de Turing es, por definición, el conjunto de cadenas que acepta. Cuando se da una entrada a la máquina, se acepta o no. Cualquier entrada particular a esa máquina siempre se acepta (en el idioma) o siempre no se acepta (no en el idioma). Por lo tanto, no existe un mecanismo por el cual una sola máquina de Turing pueda aceptar más de un idioma.

David Richerby
fuente
66
"Por definición" es exactamente lo que hubiera dicho.
Dave Clarke
1
@DaveClarke Por supuesto, es por definición. Pero esto me parece un poco corto, ya que también dice que podríamos hacer que nuestra definición sea diferente, de modo que una TM acepte dos idiomas, o cualquier número. De hecho, no estoy de acuerdo con la declaración de David Richerby de que no existe un mecanismo por el cual una TM pueda aceptar dos idiomas: es solo porque elegimos ignorarlos, y podríamos hacer lo contrario. Por lo tanto, la pregunta no se responde completamente, en mi humilde opinión, si no explicamos qué justifica hacerlo.
babou
2
Creo que el problema aquí es el lenguaje que se usa para describir el "lenguaje" en sí. Una máquina de Turing acepta cualquier cosa en forma de cadena, independientemente de nuestra definición de lenguaje. El TM define el lenguaje por lo que acepta, esto no es lo mismo que nuestra comprensión (humana) del lenguaje. Es por eso que esta respuesta es buena y es "... totalmente respondida".
David Barker
2
Estoy de acuerdo con David, el OP probablemente leyó en alguna parte que las máquinas de Turing admiten solo un idioma y está tratando de entender lo que eso significa. Dado que esto probablemente proviene de una fuente normal, podemos suponer que estaban usando la definición normal de "lenguaje" como se define en la teoría computacional, y no cualquier otra definición. La definición puede ser arbitraria, pero es una definición arbitraria bien entendida y acordada.
Cort Ammon
3
Una máquina de Turing que acepta dos idiomas es una máquina de Turing que acepta un idioma que es la unión de dos idiomas.
Simon Richter
9

Piénselo de esta manera: una TM es como una computadora con un software cargado. Cada software hace una cosa, ¿verdad? Por ejemplo, piense en su computadora y suponga que solo tiene 1 programa cargado. Entonces PC + "photoshop" solo hace photoshop, mientras que PC + "mine sweeper" solo barre las minas.

Entonces, una máquina de Turing es una criatura muy simple, que en cada ejecución obtiene una sola entrada y emite un o un no . En qué entradas dice que sí, y en qué dice que no, esto lo establece el "programa" de la TM según lo determinado por sus estados y función de transición. Una vez que estos están arreglados, el "programa" está arreglado, y para cualquier entrada dada solo hay una respuesta: o No (aceptar / rechazar). Esto define exactamente un solo idioma = todas las entradas que producen un cuando se le da a la TM.

Por otro lado, el conjunto de todas las TM es equivalente al conjunto de computadora + "software" con todos los programas posibles. Ahora se pueden decidir más idiomas, pero aún así, cada TM específica decide (o reconoce) solo un idioma.

Sonó.
fuente
Punto menor: No diría que un TM genera "ya sea un sí o un no", ya que esto descuida la no determinación. Esta simplificación podría causar más problemas más adelante.
chi
4

Turing Machine funciona como lo hacen porque elegimos definirlos así. Podríamos tener definiciones más sofisticadas, pero la pregunta es si serviría un propósito, si nos permitiría hacer más cosas. Y, hasta donde sabemos, la respuesta es no.

Es muy fácil hacer modelos de máquinas de Turing que reconocen dos idiomas. Dados los lenguajes y L 2 , podríamos definir una TM con 2 tipos de estados de aceptación: uno para L 1 y otro para L 2 . Se podría decir que un TM acepta L i si entra en algún punto en un estado de aceptación correspondiente. Pero reanudaría la computación para ver si también puede ingresar al otro tipo de estado de aceptación. Y podríamos requerir que luego se detenga, o posiblemente no. Entonces podría construir toda la teoría en tales máquinas. Funcionaría y sería mucho más complicado de lo que solemos hacer.L1L2L1L2Li

Para responder a la declaración de David Richerby de que " no existe un mecanismo por el cual una sola máquina de Turing pueda aceptar más de un idioma ", es solo porque elegimos no considerar tales mecanismos. Incluso si restringe TM al modelo estándar, podría decirse que se reconoce que la entrada está en el lenguaje cuando TM se detiene en un estado de aceptación con un número impar de pasos, y está en L 2 cuando TM acepta con un número par de pasos Gracias al no determinismo, esto no evitaría que la TM reconozca ambos lenguajes que se cruzan.L1L2

El punto es que se pueden usar todo tipo de variantes para hacer la teoría. También se han intentado enfoques muy diferentes para modelar lo que es la computación, como el cálculo lambda, la lógica de compilación, la teoría de funciones recursivas y más.

Siempre se ha demostrado que ninguno de ellos hace nada que no pueda hacer nuestro modelo simple donde TM reconoce solo un idioma. Hasta tal punto que se ha conjeturado que hace cualquier cosa que se pueda hacer. Eso se llama la tesis de la Iglesia-Turing . Es la piedra angular de la teoría de la computabilidad, que, hasta donde sabemos, determina qué lenguajes son reconocibles o no.

Por lo tanto, podríamos usar un modelo simple, ya que uno complejo nos hará la vida más difícil, sin ningún beneficio real.

Por supuesto, a veces utilizamos otros modelos porque nos permiten comprender mejor algunos problemas.

babou
fuente
Creo que el primer párrafo es un poco engañoso. Estoy dispuesto a apostar que el OP no pregunta por qué estamos definiendo las cosas de esta manera, pero que ni siquiera sabían que era el caso. "Podríamos tener definiciones más sofisticadas, pero la pregunta es si serviría para un propósito" hace que parezca que necesitas conocer el propósito de un concepto antes de que puedas imaginar darle un nombre; en mi opinión, eso es malo forma de aprender
Curiosamente,
El OP dice que quiere saber por qué TM reconoce solo un idioma para entender otra cosa. Le estoy respondiendo, lo hacen porque los definimos de esa manera. Agrego, lo cual es cierto, que podríamos usar diferentes definiciones, pero eso no cambiaría la teoría. Esa es una manera de decirle que, sea lo que sea lo que busque, la elección de la definición es irrelevante, y el reconocimiento puede definirse para cubrir exactamente los mismos conjuntos. La razón para elegir la definición es la conveniencia y la fecundidad, y es por eso que evolucionan con el tiempo, así como la forma en que se nombran o notan los conceptos.
babou
Vale, eso tiene sentido. Creo que me opongo principalmente al uso de "sofisticado", lo que implica que es deseable una definición menos simple.
Curiosamente,
3

Me gustaría ampliar un punto en la respuesta de Richerby:

Cuando se da una entrada a la máquina, se acepta o no.

La razón de esto es que la máquina de Turing es determinista: dada la misma entrada y estado inicial, siempre hará lo mismo cada vez que la ejecute (ya sea que termine en el mismo estado de aceptación o en el mismo estado de rechazo, o realice un bucle para siempre )

Además, podemos demostrar fácilmente que cada máquina Turing reconoce exactamente un idioma:

Supongamos, por contradicción, que una máquina Turing M reconoce dos lenguajes distintos L1 y L2. Como L1 y L2 son distintos, debe existir una cadena S que esté en L1 pero no en L2 (sin pérdida de generalidad; podría ser al revés, pero la prueba procedería de la misma manera a partir de aquí con L1 y L2 intercambiados ) Ahora ejecute M en S. Si acepta, se llega a una contradicción porque S estaría en L2. Si no acepta (rechaza o repite), se llega a una contradicción porque S no estaría en L1.

Atsby
fuente
2

Una máquina de Turing reconoce un idioma porque esa es la definición de la palabra reconocer : el idioma que reconoce una máquina de Turing es el conjunto de todas las cadenas / entradas que acepta la máquina de Turing.

curiosamente
fuente
2
Bienvenido a la informática ! Su respuesta es (IMO) correcta pero no creo que se agregue a las respuestas preexistentes. Tenemos muchas preguntas sin respuesta y sería mucho más interesante y productivo responder una de esas preguntas que repetir las respuestas existentes.
David Richerby
1
¡Gracias! En realidad, al principio no vi la respuesta actualmente aceptada (que creo que es buena) porque era muy corta, y sentí que las otras respuestas no respondían la pregunta de una manera directa.
Curiosamente,
1

La respuesta a esto depende de lo que entiendas exactamente cuando te refieres a "máquina de Turing". Hay tres componentes para cualquier modelo computacional (restringido a los decisores / aceptadores aquí):

  • sintaxis,
  • semántica,
  • criterios de aceptación.

Para las máquinas de Turing, la sintaxis sería la tupla de conjunto de estados, alfabetos, función de transición, etc. La semántica sería la definición de un cálculo , es decir, cómo aplicar la función de transición para derivar el contenido de la cinta después de algunos pasos. El criterio de aceptación es decir, "cuando esto sucede, nos detenemos y el resultado es ese".

Ahora, ¿las máquinas de Turing son solo sintaxis y semántica para usted, o también incluye el criterio de aceptación? Si hace lo primero, cualquier TM puede aceptar múltiples idiomas usando diferentes criterios de aceptación; incluso puede concebir criterios de aceptación que permitan múltiples idiomas aceptados (piense en TM de dos parámetros, por ejemplo). Sin embargo, si hace lo último, no hay margen de maniobra y el criterio de aceptación habitual permite exactamente un idioma por TM (de este tipo).

La definición habitual y el uso del término en TCS incluye los tres componentes. Eso tiene sentido porque, en particular, cambiar el criterio de aceptación puede cambiar la clase de objetos que el autómata representa drásticamente , por lo que debemos fijar el criterio para saber de qué hablamos.

Como ejemplo, compare autómatas finitos y autómatas Büchi . La sintaxis y la semántica son exactamente iguales, ¡pero una acepta palabras finitas mientras que la otra acepta palabras infinitas!
Intente averiguar qué sucede si conecta el criterio de aceptación de los autómatas de Büchi en la definición de TM.

Ahora, ¿por qué el criterio de aceptación habitual es significativo? Siempre y cuando se limite al lenguaje de cadenas finitas, no cambiará mucho al tener varios idiomas por TM, en el nivel conceptual: aún podremos aceptar el mismo conjunto de idiomas. Entonces nos atenemos al modelo más simple. Sin embargo, eso no quiere decir que un modelo más complicado no pueda ser útil para modelar en aplicaciones, pero eso está más allá del alcance de TCS (que tiene autoridad definitiva).

Rafael
fuente
0

M1L1L2L1L2s1s1L1s1L2M1s1s1L2M1s1sL2sL1

MLsLMssMsL

sLMs

ATM

usuario3730788
fuente
No es necesario demostrar que una TM reconoce solo un idioma: eso es inmediato a partir de la definición de "reconocer". Dada esa definición, ni siquiera está claro qué significa para un TM aceptar más de un idioma (como supones en tu primera oración) o si alguna deducción de tal suposición (como en tu tercera oración) es válida. La prueba por contradicción solo funciona si las deducciones son herméticas: aquí, el error podría estar en la suposición acerca de cómo se comporta una TM que reconoce una TM, más que en la suposición de que tal máquina existe.
David Richerby
-2

Un lenguaje es un conjunto de cadenas. ¿No es la unión de dos idiomas L1 y L2 un conjunto de cadenas (llamémoslo L3), y entonces sería otro idioma? Luego, si la máquina Turing reconoce ambos idiomas, reconoce L3, un solo idioma.

Joe Cash
fuente
2
Pero la máquina de Turing no reconoce ambos idiomas a menos que sean realmente los mismos. Reconocer L1 significa que no acepta ninguna cadena fuera de L1; reconocer L2 significa que no acepta nada fuera de L2. Si L1 y L2 son diferentes, no puede reconocer ambos.
David Richerby
-3

ninguna otra respuesta señala la existencia de la (s) Máquina (s) Universal de Turing descrita / descubierta por primera vez por Turing en su prueba de detención. Sí, un TM acepta un único lenguaje recursivamente enumerable, pero el UTM puede reconocer cualquier lenguaje recursivamente enumerable si está codificado en la entrada junto con la cadena de entrada. entonces la pregunta tiene cierta calidad zenlike. Los TM aceptan solo un idioma y todos los idiomas codificables posibles.

vzn
fuente
44
No. Una máquina universal de Turing acepta el idioma único {METRO,XMETRO acepta X} para alguna codificación -de máquinas e insumos de Turing.
David Richerby
¿Y cómo es eso diferente de lo que está escrito?
vzn
2
Reconocer codificaciones de idiomas no es lo mismo que reconocer idiomas.
David Richerby
Sí, exactamente como se indica
vzn
1
@DavidRicherby Creo que esto es una cuestión de perspectiva. Ciertamente, se puede ver que una TM universal acepta muchos idiomas; solo escríbelo como{(metro,X)metro=METRO,...} y mira los idiomas de X para cada número fijo metro(curry / smn). Restringir las TM a un parámetro es universal, pero no es necesario.
Raphael