Что такое машинный язык Тьюринга?
Поэтому я попытался найти точное определение языка, но все статьи предполагают, что определение очевидно для всех. По-видимому, для меня это не так. Каково определение машинного языка Тьюринга?
2 ответа:
Когда вы запускаете TM, вы даете ему в качестве входных данных строку. Затем ТМ либо примет строку, либо отвергнет ее, либо замкнет цикл на машине. Язык ТМ определяется как набор всех строк, которые он принимает.
Не каждый язык является языком машины Тьюринга - это один из знаковых результатов теоретической информатики. Языки, являющиеся языками машин Тьюринга, имеют множество названий-это распознаваемые языки Тьюринга, полуразрешимые языки ирекурсивно перечисляемые языки . Вы увидите, что все эти термины используются в зависимости от контекста.
Алан Тьюринг написал статью, описывающую абстрактную концептуальную реализацию дискретного автомата (что-то, что запускает последовательность команд над несколькими дискретными временными блоками) специально для использования в вычислениях. Абстрактная модель Тьюринга - это простая лента и головка, которая может читать и писать на эту ленту. Вы можете выдавать команды для перемещения головы вперед и назад (эти команды также могут быть записаны и прочитаны с одной и той же ленты).
Это Тьюринг. Машина".
Эта простая абстрактная модель (независимо от того, думаете ли вы о ней в терминах "ленты" и "головы") оказывается очень мощной, поскольку функциональность современных компьютеров может быть описана/смоделирована этим абстрактным представлением.На боковом узле, для развлечения и эксперимента некоторые люди создали буквальные реализации, близкие к оригинальному описанию tape & head "машины Тьюринга" из таких сумасшедших вещей, как legos: https://www.youtube.com/watch?v=cYw2ewoO6c4 интересная концепция заключается в том, что это безумно простое создание может сделать все, что могут сделать лучшие суперкомпьютеры (но может занять немного больше времени и legos)