1552498
Description
Mind Map by carlos lopera, updated more than 1 year ago
|
Created by carlos lopera
over 10 years ago
|
|
Máquinas de Turing "Carlos
Mario Lopera"
- Que es ?
- Es un dispositivo teórico que
manipula símbolos sobre una
cinta de acuerdo con una tabla de
reglas definidas
- reglas
- despues del primer
movimiento puede ser
leida y escrita hacia
izquierda o derecha
- moviendose a la
derecha, Γ alfabeto de
la cinta y es leida hacia
izquierda o derecha
- despues del primer
movimiento puede ser
leida y escrita hacia
izquierda o derecha
- de una manera formal o
matemáticamente son
definidas como una 7 tupla
- Σ
alfabeto
de
transición
- parte de
vocabulario
- parte de
vocabulario
- Γ
Alfabeto
de la
cinta
- Q
conjunto
de estados
- S
Estado
Inicial
- F Estados
Finales de
aceptacion
- b símbolo denominado
blanco, y es el único
símbolo que se puede
repetir un número infinito
de veces.
- δ tabla
de
estados
- Σ
alfabeto
de
transición
- reglas
- Es un dispositivo teórico que
manipula símbolos sobre una
cinta de acuerdo con una tabla de
reglas definidas
- funcionamiento y
configuracion de una
MT
- Una máquina de Turing transforma un
INPUT en un OUTPUT después de algunos
pasos. La máquina tiene un
funcionamiento totalmente mecánico y
secuencial.Lee el simbolo ->Toma el simbolo
del estado que se encuentra -> Accede a la
tabla donde lee el simbolo que debe escribir
en la cinta, el nuevo estado al que debe
pasar y si debe desplazarse a la casilla
izquierda o derecha.
- el INPUT y OUPUT
constan de números
en código binario
(ceros y unos)
- puede realizar dos
operaciones
- Mover el cabezal
lector/escritor
hacia la derecha
- Mover el cabezal
lector/escritor
hacia la izquierda
- El cabezal lee el contenido,
borra el contenido anterior
y escribe un nuevo valor.
- El cabezal lee el contenido,
borra el contenido anterior
y escribe un nuevo valor.
- Mover el cabezal
lector/escritor
hacia la derecha
- La memoria es la cinta de la
máquina que se divide en
celdas, donde se pueden
escribir y leer símbolos.
Inicialmente todas las celdas
contienen un símbolo
especial denominado
"blanco".
- el INPUT y OUPUT
constan de números
en código binario
(ceros y unos)
- Una máquina de Turing transforma un
INPUT en un OUTPUT después de algunos
pasos. La máquina tiene un
funcionamiento totalmente mecánico y
secuencial.Lee el simbolo ->Toma el simbolo
del estado que se encuentra -> Accede a la
tabla donde lee el simbolo que debe escribir
en la cinta, el nuevo estado al que debe
pasar y si debe desplazarse a la casilla
izquierda o derecha.
- Tipos de
MT
- Deterministas
- En el caso de que para
cada par (estado,
símbolo) posible exista a
lo sumo una posibilidad
de ejecución.
- En el caso de que para
cada par (estado,
símbolo) posible exista a
lo sumo una posibilidad
de ejecución.
- No
deterministas
- acepta una cadena si cualquier
secuencia de transiciones conduce a un
estado final, tambien En el caso de que
exista al menos un par (estado,
símbolo) con más de una posible
combinación de actuaciones
- acepta una cadena si cualquier
secuencia de transiciones conduce a un
estado final, tambien En el caso de que
exista al menos un par (estado,
símbolo) con más de una posible
combinación de actuaciones
- Deterministas
- sus
componentes
son
- cinta
- cabezal
- tabla
- Registro
de
estado
- cinta
Want to create your own Mind Maps for free with GoConqr? Learn more.