icono letras

Máquinas de Turing

Lenguaje AMT

  1. nl
    salto de línea
  2. nls
    • ε
    • nlnls
  3. sp
    espacio
  4. sps
    • sp
    • spsps
  5. symbol
    Unicode character
  6. symbols
    • symbol
    • symbol, symbols
  7. letterL
    letra minúscula del alfabeto latino
  8. letterU
    letra mayúscula del alfabeto latino
  9. symbol-var
    letra griega minúscula
  10. symbol-vars
    • symbol-var
    • symbol-var, symbol-vars
  11. m-config-var
    • letterU
    • Ä
    • Ö
    • Ü
  12. m-config-vars
    • m-config-var
    • m-config-var, m-config-vars
  13. name
    • letterL
    • letterLname
  14. m-function
    name(cs-variables)
  15. cs-variables
    • mconf-vars
    • symbol-vars
    • mconf-vars, symbol-vars
  16. m-config
    • name
    • m-function
  17. configuration
    m-configspssymbol
  18. operation
    • L
    • R
    • E
    • Psymbol
  19. operations
    • operation
    • operation, operations
  20. behaviour
    • operationsmcfinal
    • mcfinal
  21. skeleton-uses
    • mcfinal
    • mcfinal, skeleton-uses
  22. mcfinal-vars
    • skeleton-uses
    • ;symbols
    • skeleton-uses;symbols
  23. mcfinal
    • name
    • name(mcfinal-vars)
  24. symb-behav
    spssymbolbehaviour
  25. symb-behavs
    • symb-behav
    • symb-behavnlssymb-behavs
  26. table-inst
    • configurationbehaviour
    • m-confignls{nlnlssymb-behav nls}
  27. instructions
    • table-inst
    • table-instinstructions
  28. table
    • ε
    • instructions

Símbolos

Puede ser cualquier símbolo que se pueda representar con un codepoint Unicode; en el caso de las letras griegas se puede usar tanto su nombre como su símbolo (por ej. ‘alfa’ o ‘α’). Además se pueden usar:

Any
Cualquier símbolo leído por la máquina.
None
Ningún símbolo.
...
Cualquier símbolo o no símbolo.
not symbol
Cualquier símbolo menos symbol
not symbol1 nor symbol2
Cualquier símbolo menos symbol1 o symbol2
::
Se considera un solo símbolo.
sw
Se sustituye por el símbolo ‘ə’.
‘0’ o ‘1’ precedido por ‘-’
El símbolo con una barra encima.

Operaciones

Si no se indica ninguna operación se pasa a la siguiente m-configuration sin hacer nada. Si hay, el significado es el siguiente:

R
La máquina pasa a leer el símbolo de la derecha del que lee actualmente.
L
La máquina pasa a leer el símbolo de la izquierda del que lee actualmente.
E
Se borra el símbolo de la posición leída.
Psymbol
Se imprime en la posición actual el símbolo symbol.

Nombres m-configurations

Los nombres deben estar formados por caracteres del alfabeto español o guiones, empezanado por una letra minúscula. Adicionalmente pueden acabar con cualquier número de comillas simples, seguidas a su vez de cualquier número de dígitos.

Ejemplos

    1. 1
    b None P0, R c

    En la m-configuration ‘b’, si no hay ningún símbolo en la posición actual se imprime ‘0’ y se pasa a leer la posición de la derecha de la actual; la siguiente m-configuration será ‘c’.

    1. 1
    2. 2
    3. 3
    4. 4
    5. 5
    6. 6
    b { None P0 b 0 R, R, P1 b 1 R, R, P0 b }

    En la m-configuration b:

    • Si no hay símbolo en la posición actual se imprime «1» y pasa a la m-configuration b.

    • Si se lee «0» desplaza el lector dos posiciones a la derecha, imprime «1» y pasa a la m-configuration b.

    • Si se lee «1» desplaza el lector dos posiciones a la derecha, imprime «0» y pasa a la m-configuration b.

    1. 1
    2. 2
    3. 3
    4. 4
    f(C, B, α){ ə L f1(C, B; α) not α L f(C, B; α) }

    Definición de un skeleton.

    1. 1
    c3(C) β pe(C; β)

    Error
    La m-configuration inicial no debe estar precedida por ningún espacio.

    1. 1
    c3(C) β pe(C; β)

    Ejemplo anterior corregido.
    En la m-configuration c3(C) lee cualquier símbolo y pasa a la m-configuration pe(C, beta), donde beta es cualquier símbolo leído en el momento de cambiar de m-configuration.

    1. 1
    2. 2
    3. 3
    4. 4
    5. 5
    c2(C, A, γ) { γ C not γ A }

    Error
    La llave de apertura que ocupa una línea no debe tener espacios antes.
    Las líneas que comienzan con un símbolo deben empezar con algún espacio.

    1. 1
    2. 2
    3. 3
    4. 4
    5. 5
    c2(C, A, γ) { γ C not γ A }

    Ejemplo anterior corregido.

    1. 1
    cr(B, α) cr(cr(B, α), re(B, a, α); α)

    Error
    Debe haber algún símbolo o, en caso de que no haya acciones, 3 puntos para indicar que no hay símbolo.

    1. 1
    cr(B, α) ... cr(cr(B, α), re(B, a, α); α)

    Ejemplo anterior corregido.
    Pasa de una m-configuration a otra con cualquier símbolo y sin símbolo.