Representação de alto nível de uma Máquina de Turing

---

Ideal para representar Máquinas de Turing complexas com dezenas, centenas ou até milhares de estados.

Exemplo:

$L=\{\omega \in \{0,1{\}}^{\ast }|\omega \text{seja muˊltiplo de 4}\}$

A implementação, em alto nível, de uma Máquina de Turing que decide a linguagem L é:

MT1 = “Para um palavra $\omega \in \{0,1{\}}^{\ast }$: 1. Consulte as 2 últimas letras de $\omega$. a. Se $\omega =ϵ$, rejeite b. Se ele for 0, aceite. Caso contrário, rejeite”

NOTE

MT1 = Máquina de Turing 1 (um nome de variável qualquer)

Esclarecendo:

• A primeira linha (Para um palavra $\omega \in \{ 0, 1 \}^*$:) descreve o formato da palavra (tanto aceitação quanto rejeição)

• E as demais indicam as condição de aceitação e rejeição

Referências

---