máquina de turing

5/8/2018 máquina de turing - slidepdf.com

http://slidepdf.com/reader/full/maquina-de-turing-559bf44a1c823 1/3

http://www.mitecnologico.com/Main/LaMaquinaDeTuring

Definición Una máquina de Turing con una sola cinta puede ser definida como una 6-tupla M=(Q,L,s,b,F,o) , donde; Q es un conjunto finito de estados.

L es un conjunto finito de símbolos de cinta, el alfabeto de cinta.

s E Q es el estado inicial.

b E L es un símbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces. F _C Q es el conjunto de estados finales de aceptación.

o : Q x L ? Q x L x {L,R} es una función parcial denominada función de transición, donde L es un movimiento a la izquierda y R es el movimiento a la derecha.

¿QUE SON Y COMO FUNCIONAN? Una máquina de Turing consiste, básicamente, en una cinta infinita, dividida en casillas. Sobre esta cinta hay un dispositivo capaz de desplazarse a lo largo de ella a razón de una casilla cada vez. Este dispositivo cuenta con un cabezal capaz deleer un símbolo escrito en la cinta, o de borrar el existente e imprimir uno nuevo en su lugar. Por último, contiene además un registro capaz de almacenar un estadocualquiera, el cual viene definido por un símbolo. Los símbolos que definen el estado del dispositivo no tienen por que coincidir con los símbolos que se pueden leero escribir en la cinta.

castores afanosos

En la teoría de la computabilidad, un castor ocupado (de la expresión coloquial parauna persona "trabajadora") es una máquina de Turing que alcanza el máximo de "ocupaciones operativas" (por ejemplo, medido por el número de pasos realizados, o el número de símbolos no están en blanco en el último la cinta) entre todas las máquinas de Turing en una clase determinada. Las máquinas de Turing en esta categoría deben cumplircon ciertas especificaciones de diseño y están obligados a detener el tiempo despuésde haber comenzado con una cinta en blanco. Una función de castor ocupado cuantifica estos límites superiores en un determinadotipo de "ocupaciones operativas", y es una función noncomputable. De hecho, una función de castor ocupado se puede demostrar que crecen más rápido que lo hace asintóticamente cualquier función computable. El concepto fue introducido por primera vez po

r Tibor Radó como "juego del castor ocupado" en su artículo de 1962, "Sobre las funciones no computables".

El juego del castor ocupado

El juego de n-estado castor ocupado (o BB-n del juego), introducido en 1962 Tibor Rado papel, consiste en una clase de máquinas de Turing, cada miembro de que serequiere para cumplir con las especificaciones de diseño siguientes:La máquina tiene n estados de operación más un estado de Halt, donde n es un entero

positivo, y uno de los estados n se distingue por ser el estado inicial.(Normalmente, los estados están etiquetados con 1, 2, ..., n, con un estado comoel estado inicial, o por A, B, C, ..., con un estado como el estado de partida.

)La máquina utiliza un sencillo de dos manera infinita (o ilimitado) de la cinta.El alfabeto de la cinta es de {0, 1}, con 0 en calidad de símbolo en blanco.



Función de la máquina de transición tiene dos entradas:1.El actual no Halt Estado,2.El símbolo en la celda actual de la cinta,y produce tres salidas: 1.a símbolo para escribir sobre el de la celda actual dela cinta (que puede ser el mismo símbolo que el sobrescrito uno),2.a dirección de movimiento (izquierda o derecha, es decir, pasar a la celda de

la cinta de un lugar a la izquierda oa la derecha de la celda actual), y

3.a estado de transición a la (que puede ser el estado Detener).La función de transición puede ser vista como una tabla finita de 5-tuplas, cada una de la forma (estado actual, actual símbolo, símbolo de escribir, la dirección del cambio, el estado siguiente)."En marcha" la máquina consiste en arrancar en el estado inicial, con la celda actual de la cinta que cualquier célula de un espacio en blanco (todo-0) de cinta, yluego iterando la función de transición hasta que el estado alto es introducido (onunca). Si y sólo si, la máquina se detiene el tiempo, entonces el número de 1s finalmente restante en la cinta se llama puntuación de la máquina. El n-estado ocupado castor (BB-n) del juego es un concurso para encontrar ese n-estado de la máquina de Turing con la mayor puntuación posible - el mayor número de 1s

en la cinta después de la detención. Una máquina que obtiene la mayor puntuación posible entre todas las máquinas de Turing n de estado que se llama un castor ocupado nde estado, y una máquina cuyo resultado no es más que el más alto alcanzado hasta ahora (quizás no el más grande posible) se llama un campeón n de estado de la máquina. Radó requiere que cada equipo inscrito en el concurso de ir acompañada de una declaración del número exacto de pasos que se necesita para alcanzar el estado de Halt, permitiendo así que la puntuación de cada entrada que se verifica (en principio) por el funcionamiento de la máquina por el número indicado de pasos. (Si las entradas iban a consistir sólo en las descripciones de la máquina, entonces el problema de la verificación de todas las posibles entradas es indecidible, ya que es equivalente alconocido problema de la detención - que no habría manera eficaz de determinar si una máquina arbitraria finalmente se detiene.)

The busy beaver game The n-state busy beaver game (or BB-n game), introduced in Tibor Radó's 1962 paper, involves a class of Turing machines, each member of which is required to meetthe following design specifications:The machine has n "operational" states plus a Halt state, where n is a positiveinteger, and one of the n states is distinguished as the starting state.(Typically, the states are labelled by 1, 2, ..., n, with state 1 as the starting state, or by A, B, C, ..., with state A as the starting state.)

The machine uses a single two-way infinite (or unbounded) tape.The tape alphabet is {0, 1}, with 0 serving as the blank symbol.The machine's transition function takes two inputs:1.the current non-Halt state,2.the symbol in the current tape cell,and produces three outputs: 1.a symbol to write over the one in the current tape cell (it may be the same symbol as the one overwritten),2.a direction to move (left or right; that is, shift to the tape cell one placeto the left or right of the current cell), and3.a state to transition into (which may be the Halt state).The transition function may be seen as a finite table of 5-tuples, each of theform (current state, current symbol, symbol to write, direction of shift, next state).

"Running" the machine consists of starting in the starting state, with the current tape cell being any cell of a blank (all-0) tape, and then iterating the transition function until the Halt state is entered (if ever). If, and only if, the



machine eventually halts, then the number of 1s finally remaining on the tape iscalled the machine's score. The n-state busy beaver (BB-n) game is a contest to find such an n-state Turingmachine having the largest possible score the largest number of 1s on its tape after halting. A machine that attains the largest possible score among all n-state Turing machines is called an n-state busy beaver, and a machine whose score is

merely the highest so far attained (perhaps not the largest possible) is calleda champion n-state machine. Radó required that each machine entered in the contest be accompanied by a statement of the exact number of steps it takes to reach the Halt state, thus allowingthe score of each entry to be verified (in principle) by running the machine forthe stated number of steps. (If entries were to consist only of machine descriptions, then the problem of verifying every potential entry is undecidable, because it is equivalent to the well-known halting problem there would be no effective way to decide whether an arbitrary machine eventually halts.)

máquina de turing

Documents