Máquina de Turing, como modelo de programas de autómatas.
1. Introducción
La programación necesita nuevos modelos algorítmicos universales, y el hardware implementa algoritmos no solo en una forma diferente, sino también en base a otro modelo algorítmico: automático. Adoptar tecnología del campo del desarrollo de hardware es una idea clave de la programación automatizada. Sin embargo, la síntesis de dispositivos digitales es diferente de la programación. Pero, tomando prestado un modelo, por un lado, no es aconsejable cambiarlo sustancialmente, pero, por otro lado, no se puede ignorar la teoría y la práctica existentes de la programación.
A continuación, consideraremos la tecnología SWITCH para diseñar programas automatizados, en los que se encuentre con dichos procesos todo el tiempo. Por un lado, cambió tanto el modelo de máquina de estado que en realidad lo llevó más allá del alcance de la teoría de los autómatas. Y, por otro lado, introduce en la programación conceptos que son difíciles de percibir para los programadores y, a veces, son simplemente superfluos, porque Hay contrapartes más familiares de la teoría de programas y la práctica de programación.
Como base para la discusión de problemas de programación automática, tomamos la reciente conferencia de A. Shalyto [1] y sus artículos "programáticos" sobre la definición del paradigma de la programación automática [2, 3].
1. Objetos automatizados, esquemas de programa.En la conferencia, el logro de la programación automática es la introducción del concepto de objetos de control automatizado, tomado de la teoría del control automático (TAU). Pero recuerde que en TAU consideran no tanto objetos, sino sistemas, entre los cuales se distinguen los siguientes [4]:
En base a esto, sería más correcto hablar sobre sistemas de control automático (ACS). Ahora veamos el diagrama funcional típico de las armas autopropulsadas que se muestran en la Fig. 1. Si se considera que la cinta de la máquina de Turing es el objeto de control, los dispositivos de accionamiento (IS) serán los elementos MT que implementarán el cambio en el contenido de la cinta y moverán el cabezal, y los dispositivos de medición (IS) serán los elementos que leerán la información de la cinta.
Fig.1. Diagrama funcional de cañones autopropulsadosPero, ¿por qué recurrir a TAU si hay una práctica más cercana a la programación del diseño de sistemas informáticos, en la que los dispositivos operativos (OS), que, por supuesto, incluyen MT, se consideran una combinación de máquinas operativas (OA) y de control (UA). Y esto está más cerca de lo que finalmente buscamos: justificar el poder de la programación automática. En la fig. 2 muestra una pantalla de texto de una monografía de Mayorov S.A., Novikov G.I. La estructura de las computadoras electrónicas [5], en la que los problemas de diseño de los amplificadores operacionales se consideran con gran detalle.
Fig.2. El concepto de gerente y operación de máquinasPero, si comparamos la teoría del diseño por computadora y la teoría de los programas, entonces se puede rastrear una analogía estructural obvia entre ellos. En teoría de la programación, el modelo de cualquier programa a nivel estructural puede representarse como un esquema de programa S = (M, A, C), donde M es el conjunto de elementos de memoria, A es el conjunto de operadores, C es el control [10]. Siguiendo este enfoque, cualquier programa de máquina de Turing también se puede definir como un esquema de programa en el que el conjunto M está representado por celdas de cinta, el conjunto de operadores por acciones de MT asociadas con 1) análisis de celdas, 2) cambio de caracteres en las celdas de cinta y 3) movimiento del cabezal.
Por lo tanto, el concepto de un esquema de programa es completamente análogo al concepto considerado de autómatas operacionales y de control, donde el modelo de UA es el modelo de la máquina de estado finito estructural (SKA) considerado a continuación, y OA es una estructura para realizar acciones sobre la información. En este caso, OA incluye elementos de almacenamiento de datos (arriba es la memoria) y bloques para procesar información que implementa el cálculo de condiciones lógicas y la implementación de ciertas acciones (arriba - muchos operadores).
De lo anterior, puede entenderse que la cinta solo puede considerarse condicionalmente el objeto de control para MT. Aunque solo sea porque el dispositivo de control de la máquina Turing no tiene acceso directo a él, porque Todas las operaciones con celdas se realizan indirectamente por bloques OA. Además, parece que no es muy familiar o, si no quiere decir, es extraño considerarlo como el objetivo de la gestión del programa, como sistema de control, un objeto que representa una memoria (cinta).
Por lo tanto, para una definición formal de una máquina de Turing, y en su contexto un lugar para un modelo de máquina de estados finitos, los conceptos de teoría de programas son suficientes. Ahora, en contraste con la definición muy vaga de los programas de autómatas que se ofrecen en el marco de la tecnología SWITCH, podemos decir que un programa de autómatas es un programa que tiene control en forma de un modelo de máquina de estados finitos.
Cuál será el programa en sí mismo, con un comportamiento simple o complejo, cuál es su "variedad", con control lógico, "con asignación explícita de estado", etc. etc. No importa en absoluto. Lo principal es el tipo de gestión. Los elementos restantes del programa se pueden determinar en una amplia gama, desde los más simples, como, por ejemplo, con una máquina de Turing, hasta los más complejos, cualquier forma de operadores, funciones y estructuras de datos de lenguajes de programación: ensamblador, lenguaje de alto nivel, etc.
También puede recordar que una máquina de Turing ha sido considerada durante mucho tiempo alfombra automática [6] o, en casos extremos, su simple extensión [7]. Pero debe comprender qué tipo de autómata es, qué tipo de extensión es y si son equivalentes a los modelos de máquinas clásicas de estados finitos. Tratemos de aclarar esto.
2. Programación de Turing en un entorno de programación automatizado.En la fig. La Figura 3 muestra el autómata para la función de incremento MT de la monografía [8]. En la forma, esto claramente no es un programa MT, pero ya no es una máquina clásica de estados finitos. En la fig. La Figura 4 muestra el gráfico de la máquina clásica de estado finito estructural (SKA) y su implementación en el entorno VKPa (el entorno de programación automatizada de componentes visuales en C ++ en el marco de la biblioteca Qt y el entorno Qt Creator), que implementa el mismo algoritmo de unidad de control MT.
Fig.3. Aumente el número por unidad usando una máquina Turing
Fig. 4 Modelo de programa de incremento para MT en forma de SKAPuede ver que la máquina estructural tiene cuatro canales de entrada y cinco de salida. Cada uno de estos canales está asociado con una función de programa del mismo nombre: un predicado o acción. Aquí, los predicados son funciones sin parámetros que devuelven un valor booleano dependiendo del valor de la celda de cinta que están viendo, y las acciones son funciones sin parámetros que realizan una u otra acción para cambiar la celda de cinta y mover el cabezal de la máquina Turing.
Este SKA tiene el mismo conjunto de estados que el autómata de la figura 3. Además, además del mapeo del autómata, presentado por SKA, implementa dos mapeos más: mapeando el conjunto de predicados (x1, ..., xM) al conjunto de canales de entrada de la misma máquina, y el conjunto de canales de salida de la máquina al conjunto de las mismas acciones: y1, ..., yN. Por ejemplo, el predicado x3 devolverá verdadero (valor 1 para la señal de entrada del mismo nombre) si hay un 1 en la celda actual, y la acción y4, que se activará cuando la misma señal de salida de la máquina tome el valor 1, corresponderá a mover la cabeza hacia la izquierda (L) y etc. etc.
Tenga en cuenta que el SKA no controla directamente la cinta, sino que implementa asignaciones [adicionales], que vinculan las señales del autómata con las funciones que determinan las muchas operaciones de la máquina Turing. Esto nos convence una vez más de que no es necesario introducir el concepto de un objeto de control automatizado en una situación en la que el concepto de mapeo "anticuado" pero matemáticamente riguroso es suficiente.
Comparando los autómatas en la Fig. 3 y la fig. 4, se puede ver que SKA no utiliza el comando "*" (ver Fig. 1). En tal situación, es suficiente para él no dar una señal asociada con este comando. Además, dos o más señales (tanto de entrada como de salida) en la misma transición son paralelas. Por lo tanto, cuando hay un conflicto de acceso a objetos compartidos (por ejemplo, necesita cambiar la celda y mover la cabeza), se utiliza un acuerdo: las acciones en una transición se realizan secuencialmente en el orden de sus números, es decir. Una acción con un número más alto se realiza después de una acción con un número más bajo. Este acuerdo no se aplica a predicados, ya que No cambian la cinta. Por lo tanto, hacemos que la máquina sea más compacta e intuitiva (no es necesario introducir estados intermedios).
En el proceso de probar el programa de incremento, se identificaron situaciones en las que pueden surgir problemas durante la operación del MT. Primero, la cinta real no es infinita e ir más allá puede hacer que un programa se bloquee. En segundo lugar, es necesario indicar la posición inicial de la cabeza. Sin esto, si, por ejemplo, el número está en un lugar arbitrario de la cinta, y el estado inicial de la cabeza está a la izquierda del número y enfrente del espacio, entonces la cabeza comenzará a moverse inmediatamente hacia la izquierda. Luego puede ir más allá de los límites de la cinta, provocando que el programa se "bloquee" o, tras moverse un paso hacia la izquierda, escriba en la celda 1 y, colgando, completará la operación "exitosa". O, si el número contiene 1 en todos los dígitos y está escrito desde el principio de la cinta, entonces el intento final de transferir 1 al dígito principal causará el mismo "bloqueo".
2.1. Implementación de objetos de MT en C ++Considere la implementación del software objeto de una máquina Turing en C ++ en el entorno VKPa, que implementa cualquier programa para MT, incluido el programa de cálculo de incrementos.
Para este propósito, se ha creado una clase base que representa cualquier máquina de Turing, que es heredada por los objetos de software que implementan uno u otro programa MT. Este básico se muestra en el Listado 1, y el programa que implementa la tarea de incremento se muestra en el Listado 2.
Listado 1. Implementación de software de la clase base MT
#include "lfsaappl.h" class FTuringMashine : public LFsaAppl { public: FTuringMashine(string strNam, CVarFsaLibrary *pCVFL, LArc* pTBL); protected: int x15(); int x16(); void y14(); void y15(); void y16(); void y17(); QString strSrc;
Listado 2. Programa de incremento para una máquina Turing
#include "FTuringMashine.h" class FTIncrement : public FTuringMashine { public: LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FTIncrement(nameFsa, pCVarFsaLibrary); } FTIncrement(string strNam, CVarFsaLibrary *pCVFL); protected: int x1(); int x2(); int x3(); void y1(); void y2(); }; #include "FTIncrement.h" static LArc TBL_TIncrement[] = {
2.2. Ejemplos de programas para MT con implementación en C ++Considere un ejemplo de un programa para MT que "actúa como un aceptador del lenguaje, es decir puede reconocer el lenguaje "de [9]. Su función de transición se muestra en la Fig. 5, y el autómata equivalente en forma de SKA en la Fig. 6)
δ(1, a) = (2, x, R) δ(1, y) = (4, y, R) δ(2, a) = (2, a, R) δ(2, y) = (2, y, R) δ(2, b) = (3, y, L) δ(3, y) = (3, y, L) δ(3, a) = (3, a, R) δ(3, x) = (1, x, R) δ(4, y) = (4, a, R) δ(4, #) = (F, #, L)
Fig. 5. La función de transición de la máquina Turing, reconociendo el lenguaje {anbn: n≥1}
Fig. 6. Gráfico SKA de una máquina Turing que reconoce el idioma {anbn: n≥1}La unidad de control MT en forma de SKA tiene 6 canales de entrada y 7 de salida. El programa aceptor también incluye el número correspondiente de predicados y acciones, que se presentan en la figura a la derecha del gráfico del autómata. La implementación del programa C ++ en el entorno VKPA se muestra en el Listado 3.
Listado 3. Programa para una máquina de Turing que reconoce el idioma {anbn: n≥1}
#include "FTuringMashine.h" extern LArc TBL_TAcceptor[]; class FTAcceptor : public FTuringMashine { public: LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FTAcceptor(nameFsa, pCVarFsaLibrary); } FTAcceptor(string strNam, CVarFsaLibrary *pCVFL, LArc* pTB = TBL_TAcceptor); protected: int x1(); int x2(); int x3(); int x4(); void y1(); void y2(); void y3(); void y18(); int nState{1}; friend class CDlgTAcceptor; }; #include "stdafx.h" #include "FTAcceptor.h" LArc TBL_TAcceptor[] = {
En el Listado 3, la acción y18 representa una variante del programa MT de acuerdo con el enfoque de tecnología SWITCH. Como parte de la implementación de la programación automática del entorno VKPA, en este caso, en lugar del autómata de la Fig. 6, será necesario implementar un autómata con un estado, que emite una señal y18 en el ciclo. Corresponde a la línea comentada de la tabla de conversión en el Listado 3. Para que la máquina automática funcione como SWICH, debe eliminar el comentario de esta línea y comentar las líneas restantes.
Considere otro ejemplo de un programa para una máquina de Turing de [7], donde MT se define como "una extensión muy simple de un modelo de máquina de estado finito". En este caso, el programa para la máquina de Turing es una lista finita de cinco de la función parcialmente definida de transiciones y salidas δ: S × XS × X × G.
El programa MT, que encuentra el mayor divisor común (MCD) de dos números, se muestra en la Fig. 7. El gráfico SKA equivalente se presenta en la Fig. 8. Tenga en cuenta que el comando de reescritura tampoco se usa aquí. La implementación de C ++ se muestra en el Listado 4.
Fig. 7. El gráfico de transición de una máquina de Turing que calcula el MCD de dos números y varias de sus configuraciones al procesar un par de números <4, 6>
Fig. 8. El gráfico SKA, equivalente al gráfico de la Fig. 7 7Listado 4. Programa para una máquina de Turing para encontrar el MCD de dos números
#include "FTuringMashine.h" class FTGrCmDiv: public FTuringMashine { public: LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FTGrCmDiv(nameFsa, pCVarFsaLibrary); } FTGrCmDiv(string strNam, CVarFsaLibrary *pCVFL); protected: int x1(); int x2(); int x3(); int x4(); void y1(); void y2(); void y3(); void y17(); }; #include "FTGrCmDiv.h" static LArc TBL_TGrCmDiv[] = {
En conclusión, otro programa de MT de los desarrolladores de SWITH-technology, considerado en el artículo [11], que presenta la tarea de reconocer paréntesis en dos versiones. Uno tiene la forma de una máquina Miley, el segundo es una máquina mixta (respectivamente en la Fig. 9 y la Fig. 11). Los autómatas estructurales correspondientes a ellos se muestran en la Fig. 10 y la fig. 12. La implementación del programa C ++ se muestra en el Listado 5.
Fig. 9. Reconocimiento de paréntesis de profundidad arbitraria. Gráfico de conversión de millas
Fig. 10. Reconocimiento de paréntesis de profundidad arbitraria. Earl SKA Miles
Fig. 11. Reconocimiento de paréntesis de profundidad arbitraria. Gráfico de transición de un autómata mixto
Fig. 12. Reconocimiento de paréntesis de profundidad arbitraria. Gráfico SCA de transiciones de un autómata mixtoListado 5. Programa para una máquina de Turing para reconocer paréntesis
#include "../FTuringMashine.h" class FTListing2 : public FTuringMashine { public: void MooreAction(); LFsaAppl* Create(CVarFSA *pCVF) { Q_UNUSED(pCVF)return new FTListing2(nameFsa, pCVarFsaLibrary); } FTListing2(string strNam, CVarFsaLibrary *pCVFL); protected: int x1(); int x2(); int x3(); int x4(); void y1(); void y2(); void y3(); void y4(); void y5(); int i{0}; }; #include "FTListing2.h" static LArc TBL_TListing2[] = {
Desde el autómata en la Fig. 12 se negaron a trabajar, se decidió ir a la máquina en la Fig. 9. Una máquina automática equivalente a ella en forma de SKA se muestra en la Fig. 10. Es cierto, formalmente, este es también un autómata mixto, desde el cual la señal en el estado "0" y la señal y15 en el estado "1" se dejaron desde la primera implementación (Fig. 12). La primera es necesaria durante la instalación inicial, y la señal y15 implementa un desplazamiento de la cabeza hacia la derecha para leer el siguiente carácter de la cinta. El resto del SKA corresponde a la máquina Miles en la Fig. 9)
Después del autómata en la fig. 10 fue probado con éxito, devuelto a la máquina en la Fig. 11. Y quedó claro que la señal z1_1 con el estado "1" es superflua (para el autómata de la Fig. 12 es la señal y2). El problema es que cuando encuentra el "paréntesis izquierdo", incrementa el contador en dos unidades, y cuando encuentra el "paréntesis izquierdo" no lo cambia en absoluto. Entonces, cuando se detecta el "corchete izquierdo", se llama dos veces: una en el bucle marcado x2 / y2 y la segunda vez al ingresar al estado. Y cuando se detecta un "soporte derecho", el contador primero disminuye en el bucle y luego aumenta al ingresar al estado.
La razón de este trabajo del control MT está en la interpretación incorrecta por parte de los autores del funcionamiento de un autómata tipo Moore. Aparentemente, creen que una señal con un estado en el autómata Moore se ejecuta solo cuando ingresa a este estado (vea la transición del estado “0” a “1”), pero de hecho se emite cada vez que ingresa a este estado. Incluso al pasar por un bucle. Por lo tanto, no estamos tratando con un error (¿quién no se equivocó?), Sino con un problema más serio: una interpretación incorrecta dentro del marco de la tecnología SWITH de funcionamiento de los autómatas tipo Moore. Probar el modelo equivalente mostró esto.
3. ConclusiónPara resumir, podemos decir que no hay diferencias formales entre Turing y la programación automática, como La máquina de Turing es un modelo abstracto de programas de autómatas. Solo en el último caso, se utiliza un conjunto más amplio de operadores y estructuras de datos (memoria). Ahora podemos responder con confianza la pregunta de cómo la máquina Post, como modelo de programas ordinarios, difiere de la máquina Turing, el modelo de programas automáticos. Modelo de gestión y solo eso, porque el resto: la memoria y los operadores pueden ser lo mismo.
En consecuencia, la programación ordinaria difiere de la programación automática solo en una cosa: el modelo de control. Por lo tanto, mientras que para la implementación de autómatas se utilizan operadores de control ordinarios del tipo de conmutador y no se pueden usar similares, estrictamente hablando, dicha programación se considera automática. Esto puede ser una imitación de autómatas con la pérdida de sus propiedades específicas y nada más.
Entonces, al dar una definición de los conceptos de un programa de autómatas y la programación de autómatas, no necesitamos hablar de "objetos de control automatizado", sino de programas y solo programas que tienen control en forma de una máquina de estados finitos clásica.
Y otro hecho interesante sobre el que me gustaría llamar la atención. A principios de la década de 2000, los autores expresaron su comprensión de la programación automática para una amplia audiencia. Sus artículos sobre máquinas abstractas fueron publicados en la revista PC World No. 2 de 2002 [11, 12, 13]. Se puede argumentar que a lo largo de los años, las condenas de las partes no se vieron afectadas. Aunque, quizás esto solo refleja el grado de confianza en las decisiones elegidas.
Por ejemplo, en "una nueva conferencia sobre programación automática" A. Shalyto En comparación con la "conferencia con diapositivas" anterior (hace diez años), solo se agregó un video del ejemplo basado en el "State-of-the-art" paquete Stateflow. Parece que esto confirma la exactitud de las ideas de A. Shalyto, porque lo que no se pudo implementar dentro de UniMod (el proyecto parece estar "congelado"), encarnaron los desarrolladores de Stateflow. Y, probablemente, no es tan importante quién lo hizo ...
Sin embargo, en el momento de la publicación de los artículos mencionados, los autores de la tecnología SWITCH ya sabían que la criticaban. Esto no fue un secreto desde estaba disponible en el sitio web de SoftCraft [14]. También creó secciones dedicadas a la programación automática en general y a la tecnología SWITH y a la tecnología KA en particular. Las posiciones de los autores se discutieron en el foro del sitio (estaba abierto en ese momento). Pero todo seguía sin estar convencido.
Los resultados en este momento son los siguientes. La crítica expresada con respecto a la tecnología SWITH había sido relevante y actual. También se aplica al paquete Stateflow. En la tecnología SWITH, no existía, y no existe una definición clara de programación automática, el enfoque para la implementación de autómatas no ha cambiado, el modelo en sí no es clásico, no existe un modelo de computación paralela, etc. etc. Sin eliminar estos problemas, dicha programación automatizada en el mejor de los casos reclama un papel bastante limitado.
Las razones de los problemas mencionados anteriormente son bastante claras: se ignora la teoría de los programas, se olvida la teoría de los autómatas, aunque se dicen muchas palabras buenas y correctas sobre los autómatas y sus maravillosas propiedades. Pero, de hecho, estas son otras máquinas. El autor está convencido de lo dudoso de los intentos mal concebidos de crear modelos originales. Se trata de modelos sincrónicos, reactivos y de otro tipo. Pueden ser convenientes al resolver una clase estrecha de problemas y nada más. Pero lo más grave es que se caen de la teoría de los autómatas sin tener su propia teoría. Pero el modelo fuera de la teoría es inútil y, por lo tanto, prácticamente sin sentido.
Referencias1. Shalyto A. A. Una nueva conferencia sobre programación automática. 2019, [Recurso electrónico], Modo de acceso:
www.youtube.com/watch?v=PPWTxceMutk&feature=youtu.be , gratis. Yaz Ruso (fecha de tratamiento 5 de diciembre de 2019).
2. Shalyto A.A. El paradigma de la programación automática. Boletín científico y técnico de la Universidad Estatal de San Petersburgo de Tecnologías de la Información, Mecánica y Óptica. Vol. 53. Programación automatizada. 2008, p. 3-23.
3. Shalyto A.A. El paradigma de la programación automática. Actas de la XI Conferencia de Rusia sobre Ciencia y Educación Superior "Investigación fundamental e innovación en universidades técnicas". SPbSPU. 2007, p. 202–205., [Recurso electrónico], Modo de acceso:
is.ifmo.ru/works/_2007_09_27_shalyto.pdf , gratis. Yaz Ruso (fecha de tratamiento 5 de diciembre de 2019).
4. Miroshnik I.V. Teoría del control automático. Sistemas lineales. - San Petersburgo: Peter, 2005 .-- 336 p.
5. Mayorov S.A., Novikov G.I. La estructura de las computadoras electrónicas. - L .: Ingeniería, 1979. - 384 p.
6. Minsky M. Computaciones y autómatas. M .: Mir, 1971. - 364 p.
7. Karpov Yu.G. Teoría de autómatas. - San Petersburgo: Peter, 2003 .-- 208 p.
8. Polikarpova N., A. Shalyto A. Programación de autómatas. 2ª ed., San Petersburgo.: Peter, 2011 .-- 176 p.
9. J. MacConell Análisis de algoritmos. Enfoque de aprendizaje activo. 3a edición. - M .: Technosphere, 2013 .-- 415 p.
10. Algoritmos, software y arquitectura de sistemas informáticos multiprocesador. M .: Nauka, 1982, 336s.
11. Shalyto A.A., Tukkel N.I. Desde la programación de Turing hasta la automática // MirPK. No 2.
is.ifmo.ru/?i0=works&i1=turing12. Lyubchenko V.S. Experimentos en máquinas abstractas. "PC World", número 2,3 / 02.
www.osp.ru/pcworld/2002/02/162923 ,
www.osp.ru/pcworld/2002/03/16313713. Lyubchenko V.S. De una máquina Turing a un automóvil Miley. "PC World", Nº 8/02.
www.osp.ru/pcworld/2002/08/16385614. Sitio web de SoftCraft. Usando la teoría de autómatas en la programación. [Recurso electrónico], Modo de acceso:
www.softcraft.ru/auto , gratis. Yaz Ruso (fecha de tratamiento 5 de diciembre de 2019).