En el modelo informático de Turing, ¿cómo se debe considerar el número de símbolos del alfabeto?
Con papel y bolígrafo, dominas la tabla de multiplicar y el método de acarreo. Cuando realmente calculas 328*975 por escrito, no necesitas pensar más. Solo necesitas usar el bolígrafo. operar mecánicamente sobre el papel, lo cual es una característica de las matemáticas. Otro ejemplo es resolver una ecuación lineal simple de una variable. El proceso se puede solidificar en cinco pasos: 1. Quitar el denominador según la propiedad de igualdad, 2. Quitar los corchetes según la ley distributiva de la multiplicación, 3. Mover. términos según la propiedad de igualdad, 4. Combinar términos similares según la ley distributiva de la multiplicación, el coeficiente 5 se cambia a 1. Todas las operaciones mecánicas están determinadas por la forma, y los símbolos apropiados hacen que la forma sea más clara y fácil de entender.
En la década de 1930, el matemático británico Alan Mathison Turing (1912.6-1954.6) examinó cuidadosamente el proceso de cálculo utilizando lápiz sobre papel y propuso el concepto de máquina de Turing. Una máquina de Turing es un modelo de computadora abstracta y sus principios básicos no son complicados.
La parte mecánica de la máquina de Turing incluye:
1 Cinta de papel de entrada (utilizada para entrada y salida, palabra clave: longitud infinita):
Puede ser imaginado como Una cinta de papel infinitamente larga se divide en celdas, y cada celda registra un carácter a de una determinada tabla de caracteres.
2 cabezales de lectura-escritura
El cabezal de lectura-escritura se puede mover hacia la izquierda y hacia la derecha sobre la cinta de papel. Su función es:
Leer los caracteres del. celda actual,
Borrar los caracteres de la celda actual
Escribir un carácter en la celda actual
El cabezal de lectura y escritura solo puede operar en una celda a la vez en cualquier momento.
El controlador de la figura se puede descomponer en los siguientes componentes lógicos:
3 Alfabeto
El alfabeto incluye las celdas de la cinta de entrada que pueden ser Caracteres, el El cabezal de lectura y escritura puede escribir caracteres en la celda, por ejemplo, el conjunto de caracteres es {"1", "0", " ", "=", "︺"}.
Conjunto de 4 estados
La máquina de Turing está en un estado en cualquier momento, y todos los estados constituyen el conjunto de estados {s0, s1, s2, s3, s4, s5}, que Estos incluyen
Estado de inicio s0: está en este estado al comienzo de cada ejecución.
Estado de parada s5: cuando la máquina de Turing entra en este estado, la máquina deja de funcionar. estado, el papel Los caracteres que quedan son los resultados del cálculo
5 reglas de control
El cabezal de lectura y escritura lee los caracteres de la celda actual y combina el estado actual de la máquina para determinar:
Uno: El nuevo estado de la máquina de Turing
Dos: La operación de respuesta de la máquina de Turing
Borrar: Borrar el contenido de la celda actual
Escribir: escribe un carácter en el conjunto de caracteres de la celda actual
Mover: izquierda o derecha
La operación de la máquina de Turing se puede resumir como: (( estado actual, lectura actual) --gt; (nuevo estado, escritura actual, dirección de movimiento)). Construyamos un ejemplo simple. Este ejemplo es la operación de suma de unidades binarias. Diseño de siete estados:,
s0: estado inicial
s1: summand=1
s2: summand=0
s3: Anexo , addend=1
s4: Addendum, los addend son inconsistentes
s5: Addendum, addend=0
S6: Estado de detención
La tabla de caracteres es {"1", "0", " "},
La operación de borrado significa borrar el contenido de la celda.
Las reglas que se pueden formular son las siguientes:
Este es un ejemplo sencillo. Es precisamente que los ejemplos que se pueden ver son demasiado simples y la gente no entiende el uso de la función de Turing. Cuando vemos computadoras reales procesando problemas complejos, como simulaciones de evolución cósmica, pronóstico del tiempo, etc., aplican los mismos principios, pero la diferencia radica en el orden de magnitud de los conjuntos de caracteres, conjuntos de estados y reglas de control. El poder de la máquina de Turing es también que puede construir una máquina de Turing universal: una máquina de Turing que puede simular otras máquinas de Turing.
Una máquina de Turing que resuelve un problema específico siempre tiene un número limitado de conjuntos de caracteres, conjuntos de estados y reglas de control, por lo que tiene ((estado actual, lectura actual)—gt; (nuevo estado, escritura actual, dirección de movimiento)) puede codificarse de cierta manera como una entrada específica en la cinta de papel de otra máquina de Turing. Al mismo tiempo, su estado de funcionamiento y posición también se mantienen en celdas específicas durante la simulación, de modo que la última máquina de Turing lea el control. ejecutar según el algoritmo de la máquina de Turing anterior. El concepto de máquina de Turing universal es también la idea posterior de "computadora con programa almacenable". La máquina de Turing universal más pequeña conocida es una máquina de Turing con una tabla de caracteres de 2 caracteres y un conjunto de estados de 3 estados. En teoría, la potencia de todas las computadoras actuales no puede exceder esta máquina universal mínima. Máquina de Turing, la diferencia está sólo en la eficiencia.
El título del artículo que propuso la idea de la Máquina de Turing es "Sobre la aplicación del cálculo numérico en problemas de toma de decisiones". El problema que Turing quiere resolver es, ante todo, la computabilidad de los números. , como si se puede calcular pi (π) para cualquiera de ellos. El trasfondo directo del problema es el décimo problema de Hilbert. A principios del nuevo siglo, en 1900, el matemático alemán Hilbert pronunció una famosa conferencia sobre "Problemas matemáticos" en el Segundo Congreso Internacional de Matemáticos en París, proponiendo 23 de los problemas más difíciles de la teoría matemática. está estrechamente relacionado con la resolución de estos 23 problemas. La décima pregunta también se llama pregunta de decisión. La pregunta original es: Dada una ecuación diofántica cuyos coeficientes son todos enteros racionales y contiene cualquier número de incógnitas: diseñar un proceso que pueda determinar si la ecuación se puede resolver en números racionales mediante un número finito de cálculos. La forma general de la pregunta es: ¿Existe o no hay forma de determinar si algún problema matemático definible tiene solución? Es una estrategia para estudiar la computabilidad de los números. El cálculo de números es un problema con detalles técnicos más simples. Al mismo tiempo, Turing demostró que este problema es equivalente a un problema lógicamente decidible.
Según la investigación de Turing, la computabilidad de un problema matemático es igual a la computabilidad de la máquina de Turing de este problema. Los números computables son infinitos y contables, y los números no computables son infinitos e incontables. Teoría de conjuntos moderna: la última es de orden superior a la primera. El problema de decisión de Hilbert se puede clasificar como si una máquina de Turing universal puede determinar que otra máquina de Turing se detendrá sin simular realmente otra máquina de Turing. La respuesta de Turing es no, por lo que la decisión de Hilbert El problema no tiene solución, y esto también ilustra las limitaciones de la máquina de Turing. . Unos meses antes de que Turing completara su tesis, el matemático estadounidense Alonzo Church (1903.6–1995.8) presentó el artículo "Sobre la explicación de los problemas de decisión", que también demostró que el problema de decisión no tiene solución. El método utilizado por Qiu Qi se basa en funciones recursivas y operaciones Lambda.
Aunque el principio básico de la máquina de Turing es simple, los problemas involucrados detrás de ella son bastante profundos. Muchas discusiones han continuado hasta el día de hoy y continuarán. Estas discusiones pueden reducirse a tres preguntas básicas: ¿Es el cerebro humano una máquina de Turing? ¿Es el universo una máquina de Turing? ¿Es posible diseñar una máquina que supere a la máquina universal de Turing sin violar las leyes de la física?
A partir del tema de este libro, la máquina de Turing comenzó describiendo el proceso de cálculo de las personas usando lápiz sobre papel. El cabezal de lectura y escritura de la máquina de Turing es equivalente a los ojos y las manos humanos. La entrada de cinta de papel es un problema que debe resolverse según la entrada y el estado actual, y se combina con las reglas aplicables para escribir y moverse. operaciones. Esto es diferente del lápiz humano. Las decisiones y acciones son consistentes al calcular en papel. Las operaciones atómicas de una máquina de Turing son: leer un carácter, eliminar un carácter, escribir un carácter cuando ya tiene un carácter, puede considerarse como una modificación. Lo mismo ocurre con las operaciones atómicas en el nivel físico de los medios. en aplicaciones de símbolos humanos, que pueden ser algo diferentes, por ejemplo, eliminar no significa necesariamente borrarlo, pero lo invalida al cruzarlo, y modificar significa escribir el símbolo correcto al lado después de invalidarlo. Esta diferencia no tiene un significado sustancial.
La máquina de Turing proporciona una abstracción general del cálculo: el cálculo generalizado es una operación mecánica simbólica basada en reglas. Según esta definición, una máquina de Turing puede realizar cálculos siempre que existan ciertas reglas.
Esto va más allá del concepto de cálculo en matemáticas. De hecho, las aplicaciones informáticas modernas no se ocupan principalmente de resolver ecuaciones matemáticas y los símbolos que operan no se limitan a símbolos numéricos. ¿Qué otras formas de cálculo existen? ¿De dónde vienen? La teoría de Turing no lo describía y hoy se supone que se trata de una aplicación abierta, bastante extendida y exitosa. Combinando las tres preguntas extendidas de la anterior máquina de Turing, aunque la computación se originó a partir de las matemáticas, la tendencia que se puede ver hoy es que el concepto de computación no depende de las matemáticas y, a la inversa, se puede considerar que las matemáticas dependen del concepto de computación. , y la informática se considera un paradigma o una filosofía independiente. Lo que no ha cambiado es que esto sigue siendo una manipulación de símbolos.