Modelos formales de computacion

MODELOS FORMALES DE
COMPUTACIÓN
Autómatas
Máquinas que consisten en estados y
transiciones.

M.C. BLANCA IDALIA MARTÍNEZ CAVAZOS

ALGORITMOS COMPUTACIONALES

1

MODELOS FORMALES DECOMPUTACIÓN
Transiciones



Cuando de un estado hay múltiples transiciones posibles, la
máquina
recibe como entrada símbolos de un alfabeto.
El símbolo recibido determina la transición arealizar.



Cuando hay solamente una transición posible por estado, el
alfabeto
es unario.



Si una entrada causa que el autómata llegue a un estado
terminar, su operación acaba.



Elresultado de la operación es el estado final elegido.

M.C. BLANCA IDALIA MARTÍNEZ CAVAZOS

ALGORITMOS COMPUTACIONALES

2

MODELOS FORMALES DE
COMPUTACIÓN
Autómatas Deterministas
Una solatransición posible de cada estado por
símbolo del alfabeto, no más.
a

b
c

c
b

M.C. BLANCA IDALIA MARTÍNEZ CAVAZOS

a

ALGORITMOS COMPUTACIONALES

3

MODELOS FORMALES DECOMPUTACIÓN
Autómata No Determinista

el


Cuando hay dos o más posibles transiciones de un estado que usan
mismo símbolo del alfabeto, el autómata elige su transición al azar.
La presencia dealeatoriedad se llama no determinismo.

a

b
b

b
a

M.C. BLANCA IDALIA MARTÍNEZ CAVAZOS
COMPUTACIONALES

a

ALGORITMOS
4

MÁQUINA DE TURING

M.C. BLANCA IDALIA MARTÍNEZ CAVAZOSALGORITMOS COMPUTACIONALES

5

MÁQUINA DE TURING
En matemáticas se considera que un método o procedimiento es
efectivo para obtener un resultado cuando se cumple que:
El

procedimiento puede serexpresado mediante un algoritmo (un número finito
de instrucciones concretas 1.2.1); en el que cada instrucción puede ser expresada
por un número finito de símbolos.
El

procedimiento puede serseguido sin error para conseguir el resultado en un
número finito de pasos.
El

procedimiento puede ser (al menos teóricamente) seguido por un humano sin
más ayuda que un papel y lápiz.
El...