Я много читал о машине Тьюринга и понимаю, как она работает, но чего я не могу понять (и чему ни одна из книг, кажется, не пытается научить), так это как мне подходить к проблеме, которую мне поручено решить? Я имею в виду: например, проверка того, является ли слово палиндромом, состоит из 11 состояний в книге, по которой я учусь. Для моего нынешнего уровня знаний просто сидеть над пустым листом бумаги и придумывать все эти состояния кажется почти невозможным, если не сказать больше. Когда я пытаюсь сделать что-то подобное, я сразу же застреваю, так как не знаю, что мне делать, чтобы эти состояния работали как-то «вместе». У меня нет таких проблем при программировании, но здесь я просто не могу понять, как мне подойти к чему-то, состоящему из каких-то n-teen состояний. Не могли бы вы указать мне направление, чтобы узнать об этом?
Машина Тьюринга и идея
Ответы (1)
Машины Тьюринга — это архитектурная модель, не очень далекая от машины фон Неймана. Итак, это очень низкоуровневая модель вычислений, и лучший способ решения проблемы программирования с их помощью — это тот же метод, который мы использовали бы для традиционного оборудования, а именно с помощью абстракций.
Считается, что машины Тьюринга не композиционны, но это не совсем так. Несложно совместить функцию перехода машин Тьюринга, реализующую последовательную композицию, условные операторы и циклы. Затем, начиная с небольшой библиотеки базовых машин, выполняющих сравнение символов, замену символов и подобные операции, вы можете создавать очень сложные программы.
Мы использовали этот метод, чтобы написать универсальную машину Тьюринга и подтвердить ее правильность в помощнике по проверке доказательств Matita (система, аналогичная Coq). Ссылка:
Асперти, Риччиотти «Формализация многоленточных машин Тьюринга», TCS 603, 2015.
