Включает ли полнота по Тьюрингу способность ничего не делать
Необходимо ли, чтобы языки могли представлять "ничего не делать", чтобы считаться завершенным по Тьюрингу? Если ответ "нет", то существует мыслимая программа, которая не может быть представлена / выполнена на компьютере, завершенном по Тьюрингу, но если ответ "да", полнота по Тьюрингу больше не полностью определяется способностью компьютера что-либо делать.
1 ответ
Полнота Тьюринга больше не полностью определяется способностью компьютера что-либо делать.
Я не уверен, какой учебник вы используете, который дает это определение полноты по Тьюрингу.
Говорят, что язык программирования является полным по Тьюрингу, если его можно использовать для моделирования любой машины Тьюринга. Машина Тьюринга имеет точное математическое определение. Одной из таких возможных машин Тьюринга является машина с начальным начальным состоянием q и одно состояние остановки q, Это должно напоминать "ничего не делать" на всех заданных входах.