Итак, я попытался найти точное определение языка, но все статьи предполагают, что это определение очевидно для всех. Видимо, мне это не так. Каково определение машинного языка Тьюринга?Что такое язык машины Тьюринга?
При запуске ТМ вы указываете его как ввод строки. Затем TM примет либо строку, либо отклонит строку, либо цикл на машине. Язык ТМ определяется как набор всех строк, которые он принимает.
Не каждый язык является языком машины Тьюринга - это один из знаковых результатов теоретической информатики. Языки, которые являются языками машин Тьюринга, имеют много имен - это Turing-узнаваемые языки, полудискримируемые языки и рекурсивно перечисляемые языки. Вы увидите все эти термины, используемые в зависимости от контекста.
Alan turing написал статью, описывающую абстрактную концептуальную реализацию дискретных автоматов (что-то, что выполняет последовательность команд по нескольким дискретным блокам времени) специально для использования в вычислении. Абстрактная модель Тьюринга - это простая лента и голова, которые могут читать и записывать на эту ленту. Вы можете выдавать команды для перемещения головы назад и вперед (эти команды можно также писать и читать с одной и той же ленты).
Это «Машина Тьюринга».
Эта простая абстрактная модель (независимо от того, думаете вы ее в терминах «ленты» и «голова»), оказывается очень мощной, поскольку функциональность современных компьютеров может быть описана/смоделирована этим абстрактным представлением.
На стороне узла, для удовольствия и эксперимент некоторых людей создал буквенные реализации близко к ленте & голову оригинального описания «машина Тьюринга» из вещей, как сумасшедших, как Льи: https://www.youtube.com/watch?v=cYw2ewoO6c4 Интересного понятия, что это безумно простой создание может сделать все, что могут достичь лучшие суперкомпьютеры (но может занять немного больше времени и legos)
Это, вероятно, лучше спросить на Computer Science.SE или Theoretical Computer Science.SE. – Linuxios
https://en.wikipedia.org/wiki/Turing_machine – Alexan