Ensayo Maquina de Turing

[pic 1]UNIVERSIDAD TÉCNICA DEL NORTE    

FACULTAD DE INGENIERIA EN CIENCIAS APLICADAS  

INGENIERÍA EN SISTEMAS COMPUTACIONALES

MATERIA: Ingeniera de software 2

ESTUDIANTE: David Ortega

FECHA: 14-ago-2020

Máquina de Turing

Introducción

Las máquinas de Turing, descritas por primera vez por Alan Turing en (Turing 1937), son simples dispositivos computacionales abstractos destinados para ayudar a investigar el alcance y las limitaciones de lo que se puede calcular. Turing estaba interesado en la cuestión de qué significa que una tarea sea computable, que es una de las cuestiones fundamentales en la filosofía de la informática. Intuitivamente, una tarea es computable si es posible especificar una secuencia de instrucciones que resultarán en la finalización de la tarea cuando sean realizadas por alguna máquina. Este conjunto de instrucciones se denomina procedimiento eficaz o algoritmo para la tarea.

Desarrollo

Una máquina de Turing es una especie de máquina de estado. En cualquier momento, la máquina se encuentra en cualquiera de un número finito de estados. Las instrucciones para una máquina de Turing consisten en condiciones específicas bajo las cuales la máquina pasará de un estado a otro.

Las máquinas de Turing no son objetos físicos sino matemáticos. La arquitectura se describe de forma sencilla y las acciones que puede realizar la máquina son sencillas y se especifican de forma inequívoca. Turing reconoció que no es necesario hablar sobre cómo la máquina lleva a cabo sus acciones, sino simplemente tomar como dadas las ideas gemelas de que la máquina puede llevar a cabo las acciones especificadas y que esas acciones pueden describirse de manera única.

Una máquina de Turing procesa una cinta infinita. Esta cinta está dividida en cuadrados, cualquier cuadrado de los cuales puede contener un símbolo de un alfabeto finito, con la restricción de que solo puede haber un número finito de cuadrados no en blanco en la cinta. La máquina de Turing modela matemáticamente una máquina que opera mecánicamente en una cinta. En esta cinta hay símbolos que la máquina puede leer y escribir, uno a la vez, utilizando un cabezal de cinta. Esencialmente, una máquina de estados finitos consta de varios estados. Cuando un símbolo, digamos un carácter de algún alfabeto, se ingresa en la máquina, cambia de estado de tal manera que el siguiente estado depende solo del estado actual y del símbolo de entrada. Puede representar una máquina de estados finitos en una forma que la haga más fácil de entender y pensar. Todo lo que tiene que hacer es dibujar un círculo para cada estado y flechas que muestren qué estado sigue para cada símbolo de entrada.

...