304
правки
Изменения
м
→Результат работы: ещё интервики
=== Результат работы ===
Машину Тьюринга можно рассматривать как распознаватель слов [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками|формального языка]]. Пусть <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 \exists z \in \Pi^* : \langle \varepsilon, S, x \rangle \vdash^* \langle z, Y, y \rangle</tex>. Переход автомата в состояние <tex>N</tex> можно интерпретировать как аварийное завершение программы (например, при некорретном входе).
