Autor Tema: Máquina de Turing

0 Usuarios y 1 Visitante están viendo este tema.

19 Junio, 2009, 01:27 pm
Leído 2012 veces

matematico

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 100
  • Karma: +0/-0
  • Sexo: Masculino
Alguien me puede ayudar a realizar este ejercicio? Gracias de ante mano

Diseñar una máquina turing para un \( \epsilon_0 \) alfabeto arbitrario que compute la función f:\( \epsilon^*_0 \longrightarrow{} \){0,1} definida por f(w) = 0 si la longitud de w es par y f(w) = 1 si la longitud es impar.

Corregido el título
turing Turing (era una persona)

19 Junio, 2009, 08:01 pm
Respuesta #1

Fernando Revilla

  • "Há tantos burros mandando em homens de inteligência, que, às vezes, fico pensando que a burrice é uma ciência." -Antonio Aleixo.
  • Administrador
  • Mensajes: 11,846
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
  • "Las matemáticas son demasiado humanas."- Brouwer
    • Fernando Revilla
Con la nomenclatura usual (\( B \) celda en blando, \( D \) mover a la derecha, \( I \) mover a la izquierda), podemos primero transformar los símbolos en unos. Por ejemplo para la cinta con entrada:

\( \ldots B\;B\;\boxed{X}\;Y\;Z\;B\;B\;\ldots \;(1) \)
verifica que las cuaternas:

\( (q_0,X,1,q_0),\;(q_0,Y,1,q_0),\;(q_0,Z,1,q_0),\;(q_0,B,I,q_1),\;(q_1,1,I,q_1)\;(q_1,B,D,q_2) \)

transforman la cinta \( (1) \) en la siguiente:

\( \ldots B\;B\;\boxed{1}\;1\;1\;B\;B\;\ldots \;(2) \)

en donde hay que definir el estado \( q_2 \). Las cuaternas:

\( (q_2,1,D,q_3),\;(q_3,1,D,q_2),\;(q_3,B,D,q_4),\;(q_4,B,1,q_4) \)

transforman la cinta \( (2) \) en:

\( \ldots B\;B\;1\;1\;1\;B\;1\;B\;\ldots \;(3) \)

por haber un número impar de unos. Si en \( (2) \) hubieramos tenido un número par de unos, por haber sido el cardinal del alfabeto par, \( (2) \) se hubiera transformado en \( (3') \):

\( \ldots B\;B\;1\;1\;1\;1\;B\;B\;\ldots \;(3') \)

Ahora, es facil transformar \( (3) \) en \( \ldots B\;B\;1\;B\;B\;\ldots \;(3) \) y \( (3') \) en: \( \ldots B\;B\;0\;B\;B\;\ldots \;(3) \).

Saludos.