Máquina de Turing

Una máquina de Turing T sobre Σ es una tripla T = (K, q₀, I) donde K es un conjunto finito de estados, q₀ ∈ K es el estado inicial, e I es una función parcial I : K × (Σ ∪ {#}) → (Σ ∪ {#}) × {R, L} × K.

Instrucción

Una instrucción es una quíntupla (qᵢ, s, t, D, qⱼ) tal que:
· qᵢ, qⱼ ∈ K (estados)
· s, t ∈ Σ ∪ {#} (símbolos)
· D ∈ {R, L} (dirección)
· I(qᵢ, s) = (t, D, qⱼ)

Combinación final

Una pareja (qᵢ, s) es una combinación final si no aparece al comienzo de ninguna instrucción. La máquina se detiene al leer s en estado qᵢ.

De Castro Korgi §6.1 · slides §1–5

Icfes para disciplinados →

UNISMP →

Número Pi →

El Cóndor →

FCEN — UNAL →

Droguerías Prevensur →

Catálogo boutique Arcur →

Ludix →

Turing Machine →

Recursive Concat. →

Enum of Σ* →

Regular Expr. →

Cross Matrix →

Sorting →

Fractal →

Bernoulli →

χ² Dist. →

T-Student Dist. →

Normal Dist. →

Ruffini →

Fractions →

Voice →

Cantor Sets →

Sets →

Hill Cipher →

Minecraft Coords →

String Tool →

Tic-Tac-Toe →

Minesweeper →

Sudoku →

Icfes para disciplinados

UNISMP

Número Pi

El Cóndor

FCEN — UNAL

Droguerías Prevensur

Catálogo boutique Arcur

Ludix

Turing Machine

Recursive Concat.

Enum of Σ*

Regular Expr.

Cross Matrix

Sorting

Fractal

Bernoulli

χ² Dist.

T-Student Dist.

Normal Dist.

Ruffini

Fractions

Voice

Cantor Sets

Sets

Hill Cipher

Minecraft Coords

String Tool

Tic-Tac-Toe

Minesweeper

Sudoku