304
правки
Изменения
→Определение: описание машин-распознавателей и машин-преобразователей
* если <tex>\delta(q, B) = \langle p, y, \rightarrow \rangle</tex>, то <tex>\langle w, q, \varepsilon \rangle \vdash \langle wy, p, \varepsilon \rangle</tex>
* если <tex>\delta(q, B) = \langle p, y, \downarrow \rangle</tex>, то <tex>\langle w, q, \varepsilon \rangle \vdash \langle w, p, y \rangle</tex>
=== Результат работы ===
Машину Тьюринга можно рассматривать как распознаватель слов языка. Пусть <tex>M</tex> — машина Тьюринга, распознаваемый ей язык определяется как <tex>\mathcal L(M) = \{ x \in \Sigma^* \mid \exists y, z \in \Pi^*: \langle \varepsilon, S, x \rangle \vdash^* \langle y, Y, z \rangle \}</tex>.
Также можно рассматривать машины Тьюринга как преобразователь входных данных в выходные. Машина <tex>M</tex> задаёт вычислимую функцию <tex>f</tex>, причём <tex>f(x) = y \Leftrightarrow \langle \varepsilon, S, x \rangle \vdash^* \langle z, Y, y \rangle</tex>. Примеры машин-распознавателей и машин-преобразователей будут даны ниже.
