Небольшой C-подобный язык, который могут моделировать машины Тьюринга

Я ищу небольшой язык, который поможет «убедить» студентов, что машины Тьюринга являются достаточно общей вычислительной моделью. Это язык, который похож на языки, к которым они привыкли, но также легко моделируется на машине Тьюринга.

Пападимитриу использует машины ОЗУ для этой работы, но я боюсь, что сравнение чего-то странного (как машины Тьюринга) с другой странной вещью (в основном, языком ассемблера) будет слишком неубедительным для многих студентов.

Любые предложения будут приветствоваться (особенно если они пришли с рекомендуемой литературой)

• Если ваши ученики занимались каким-либо функциональным программированием, самый хороший подход, который я знаю, - это начать с нетипизированного лямбда-исчисления, а затем использовать теорему о скобках для перевода его в комбинаторы SKI. Затем вы можете использовать теоремы и u t m, чтобы показать, что машины Тьюринга образуют частичную комбинаторную алгебру и могут интерпретировать комбинаторы SKI.$smn$$utm$

  Я сомневаюсь, что это самый простой из возможных подходов, но мне нравится, как он опирается на некоторые из самых фундаментальных теорем вычислимости (которые вы, возможно, пожелаете охватить по другим причинам).

  Похоже, что Андрей Бауэр ответил на аналогичный вопрос о Mathoverflow несколько месяцев назад.

• Если вы настроены на C-подобный язык, ваш путь будет намного более грубым, так как они имеют довольно сложную семантику - вам нужно будет

  1. Покажите, что машины Тьюринга могут моделировать стек и кучу одновременно, и
  2. Показать, как переменные могут быть реализованы с помощью стека, и
  3. Покажите, что вызовы процедур могут быть реализованы с помощью стека.

  Честно говоря, это большая часть содержания класса компиляторов.

Моя Теория Comp профессора в бакалавриате началась с доказательства того, что одноленточная машина Тьюринга может реализовывать многоленточную машину Тьюринга. Это обрабатывает объявление переменных: если программа имеет шесть объявлений переменных, то она может быть легко реализована на машине Тьюринга с семью лентами (лента для каждой переменной и лента «регистрации», чтобы помочь выполнять такие задачи, как арифметика и проверка равенства между ленты). Затем он показал, как реализовать базовые циклы FOR и WHILE, и на тот момент у нас был базовый C-подобный язык, полный по Тьюрингу. В любом случае, я нашел это удовлетворительным.

Сейчас я думаю о том, как убедить себя, что машины Тьюринга - это общая модель вычислений. Я согласен с тем, что стандартная трактовка тезиса Черча-Тьюринга в некоторых стандартных учебниках, например, «Сипсер», не очень полная. Вот набросок того, как я могу перейти от машин Тьюринга к более узнаваемому языку программирования.

Рассмотрит блок-структурированный язык программирования с ifи whileзаявление, с не-рекурсивными определенными функциями и подпрограммами, с именованными булевыми случайными величинами и общими логическими выражениями, и с одной неограниченным булевым массивом tape[n]с указателем массива целого , nкоторое может быть увеличено или уменьшено, n++или n--, Первоначально указатель nравен нулю, а массив tapeизначально равен нулю. Таким образом, этот компьютерный язык может быть C-подобным или Python-подобным, но он очень ограничен в своих типах данных. На самом деле они настолько ограничены, что у нас даже нет способа использовать указатель nв логическом выражении. При условии, чтоtapeтолько бесконечно вправо, мы можем объявить указатель на понижение "системной ошибкой", если nкогда-либо будет отрицательным. Кроме того, наш язык имеет exitоператор с одним аргументом для вывода логического ответа.

Тогда первое, что этот язык программирования является хорошим языком спецификаций для машины Тьюринга. Вы можете легко увидеть, что, кроме ленточного массива, код имеет только конечное число возможных состояний: состояние всех объявленных им переменных, текущая строка выполнения и его стек подпрограмм. Последний имеет только конечное количество состояний, потому что рекурсивные функции не допускаются. Вы можете представить себе «компилятор», который создает «реальную» машину Тьюринга из кода этого типа, но детали этого не важны. Дело в том, что у нас есть язык программирования с довольно хорошим синтаксисом, но очень примитивными типами данных.

Остальная часть конструкции состоит в том, чтобы преобразовать это в более удобный язык программирования с конечным списком библиотечных функций и этапов предварительной компиляции. Мы можем действовать следующим образом:

1. С помощью прекомпилятора мы можем расширить логический тип данных до большего, но конечного символьного алфавита, такого как ASCII. Можно предположить, что tapeпринимает значения в этом большем алфавите. Мы можем оставить маркер в начале ленты, чтобы предотвратить переполнение указателя, и подвижный маркер в конце ленты, чтобы предотвратить случайное перемещение ТМ на бесконечность на ленте. Мы можем реализовать произвольные двоичные операции между символами и преобразования в логические выражения for ifи while. (На самом деле ifможет быть реализован с помощью while, если он не был доступен.)

2. $k$$k$$i$$i$$k$

3. Мы обозначаем одну ленту как символьную «память», а другие - как беззнаковые, целочисленные «регистры» или «переменные». Мы храним целые числа в двоичном порядке с прямым порядком байтов с маркерами завершения. Сначала мы реализуем копию регистра и двоичный декремент регистра. Комбинируя это с увеличением и уменьшением указателя памяти, мы можем реализовать поиск произвольного доступа к памяти символов. Мы также можем написать функции для вычисления двоичного сложения и умножения целых чисел. Нетрудно написать двоичную функцию сложения с побитовыми операциями и функцию умножения на 2 с левым сдвигом. (Или действительно правое смещение, поскольку оно имеет младший порядок.) С этими примитивами мы можем написать функцию для умножения двух регистров, используя алгоритм длинного умножения.

4. Мы можем реорганизовать ленту памяти из одномерного массива символов symbol[n]в двумерный массив символов, symbol[x,y]используя формулу n = (x+y)*(x+y) + y. Теперь мы можем использовать каждую строку памяти, чтобы выразить целое число без знака в двоичном виде с символом завершения, чтобы получить одномерную, целочисленную память с произвольным доступом memory[x]. Мы можем реализовать чтение из памяти в целочисленный регистр и запись из регистра в память. Многие функции теперь могут быть реализованы с помощью функций: арифметика со знаком и с плавающей запятой, символьные строки и т. Д.

5. Только еще одно базовое средство строго требует прекомпилятора, а именно рекурсивные функции. Это можно сделать с помощью техники, которая широко используется для реализации интерпретируемых языков. Мы присваиваем каждой высокоуровневой рекурсивной функции строку имени и организуем низкоуровневый код в один большой whileцикл, который поддерживает стек вызовов с обычными параметрами: вызывающей точкой, вызываемой функцией и списком аргументов.

На данный момент в конструкции есть достаточно возможностей языка программирования высокого уровня, поэтому дальнейшая функциональность - это скорее тема языков программирования и компиляторов, а не теория CS. Также уже легко написать симулятор машины Тьюринга на этом развитом языке. Это не совсем легко, но, безусловно, стандартно, написать самокомпилятор для языка. Конечно, вам нужен внешний компилятор для создания внешней TM из кода на этом C-подобном или Python-подобном языке, но это можно сделать на любом компьютерном языке.

Обратите внимание, что эта схематичная реализация не только поддерживает тезис Черча-Тьюринга для рекурсивного класса функций, но и расширенный (т. Е. Полиномиальный) тезис Черч-Тьюринга применительно к детерминированным вычислениям. Другими словами, он имеет полиномиальные накладные расходы. Фактически, если нам дается машина с ОЗУ или (мой личный фаворит) ТМ с древовидной структурой, это может быть уменьшено до полилогарифмических издержек для последовательных вычислений с ОЗУ.

Компилятор LLVM позволяет довольно просто "подключить" новую архитектуру. Они называют это написанием нового бэк-энда и дают подробные инструкции и примеры того, как это сделать. Я подозреваю, что вам придется перепрыгнуть через несколько циклов в отношении памяти с произвольным доступом, если вы не хотите ориентироваться на машину ОЗУ Тьюринга, но это определенно выполнимо, так как я видел ряд проектов, которые вызывают LLVM для генерации VHDL или другие очень разные машинные языки.

Это имело бы интересный эффект наличия современного оптимизирующего компилятора (во многих отношениях LLVM более продвинутый, чем GCC), генерирующего код для машины Тьюринга.

Я не в теории CS, но у меня есть кое-что, что может быть полезным. Я взял другой подход. Я разработал простой процессор, напрямую программируемый с небольшим подмножеством C. Нет никакого ассемблерного кода, только C-подобный код. Вы можете использовать тот же инструмент, который я использовал, и модифицировать этот процессор для разработки симулятора машины Тьюринга. У меня ушло 4 дня на разработку, моделирование и тестирование этого процессора, ну и несколько инструкций! Инструменты, которые я использовал, даже позволили мне генерировать реальный синтезируемый код VHDL. Это настоящий рабочий процессор.

Вот как выглядит программа:

Вот изображение процессора с использованием этих инструментов.

Инструменты "Novakod Studio" использует язык описания аппаратного обеспечения на языке высокого уровня. В качестве примера, вот код счетчика программы: достаточно разговоров, если кому-то интересно, вот публичная информация, чтобы связаться со мной: https://repertoire.uqac.ca/Fiche.aspx?id=JjstNzsH0&link=1

Люк

Как насчет того, чтобы принять идею, представленную здесь пользователем GMB (машина Тьюринга с одной лентой может смоделировать машину Тьюринга с N лентами, чередуя N лент на одной ленте и считывая любую из этих лент, перепрыгивая по N местоположениям за раз, машину с N лентами можно реализовать ...) и написать программу машины Тьюринга, которая реализует упрощенную RAM-машину. RAM-машина может быть на самом деле упрощенным, реальным процессором с доступным бэкэндом LLVM или GCC. Затем GCC / LLVM можно использовать для кросс-компиляции C-программы для этого ЦП, а машинная программа Тьюринга, которая имитирует RAM-машину, запускает симуляцию RAM-машины, когда симулированная RAM-машина выполняет вывод GCC / LLVM. Реализация машины Тьюринга может быть очень простым C-кодом, который подходит для небольшого C-файла.

Что касается RAM-машины, то существует демонстрационный проект, в котором 32-битный процессор моделируется 8-битным микроконтроллером, а симулированный 32-битный процессор загружает Linux. Медленно, как ад, но, по словам автора , Дмитрия Гринберга, это сработало. Может быть, Zylin CPU (пользователь GitHub zylin) может быть подходящим выбором для симулируемой RAM-машины. Другим кандидатом в RAM-машины может быть проект ProjectOberon dot com от Niklaus Wirth .

(«Точка» и «com» ​​в моем тексте связаны с тем, что я, 2015_10_21, зарегистрировал свою учетную запись на cstheory.stackexchange, а веб-приложение не допускает более 2 ссылок для начинающих пользователей, несмотря на то, что что они могут автоматически видеть из моих других учетных записей stackexchange, что я могу быть глупым, но я не тролль.)