В первую очередь - это формальное определение алгоритма. Задача считается алгоритмически разрешимой тогда и только тогда, когда её решение можно запрограммировать на машине Тьюринга (или каким-нибудь другим эквивалентным способом). Это определение даёт, например, возможность предъявить алгоритмически неразрешимые задачи. Позволяет ввести понятие "Тьюринг-полного" языка - если на языке можно реализовать машину Тьюринга, то на нём можно написать любой алгоритм (язык С таким не является, а C# - является).
В общем, МТ - способ определить некоторый класс алгоритмов:
- некоторые задачи можно решить конечным автоматом;
- для некоторых потребуется конечный автомат со стековой памятью;
- для других достаточно машины Тьюринга;
- для остальных требуется божественное откровение или другие неалгоритмизируемые методы.
Простой
