Машина тьюринга код питон

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Turing machine implementation in Python

Mdelaf/turing-machine

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

The goal of this project is to simulate Turing machine runs.

Turing machines must be defined in a text file using the same syntax used in turingmachinesimulator.com. For example, this would be a machine which only accepts odd binary numbers:

name: isOdd init: q0 accept: qf q0,0 q0,0,> q0,1 q0,1,> q0,_ q1,_,

As you might notice the machine alphabet is not defined explicitly, so every printable character (except for spaces) can be given as inputs. Another limitation is that you can’t represent a transition for every possible character (i.e Σ -transition).

Loading the turing machine

Text files who follow this syntax can be loaded using the from_file method:

from turing_machine import TuringMachine tm = TuringMachine.from_file("oddbinarymachine.txt")

If there are syntax errors the parser will raise a ParsingError exception. Comments ( // ) and empty lines will be skipped.

To simulate a run in the machine you should use the run method and pass the word as an argument:

result = tm.run("11010") # result = False

This method returns three possible values:

• True : if the run finishes in a final state (i.e the word is accepted by the machine)
• False : if the run finishes in a non-final state (i.e the word is rejected by the machine)
• None : if the run gets stucked in a configuration loop (i.e the run never ends)

If you are interested in differentiating between a rejected word and a run that doesn’t stop you should compare the result value explicitly, because both False and None are falsy values.

There is also a possibility for the machine to never stop but changing its configuration in every step, in a way that it never reaches the same configuration twice (i.e without falling in a configuration loop). If this is the case, the run method will never end.

Cases where a run doesn’t finish can’t be caught easily, so the run method accepts an optional timeout parameter. With this parameter you can specify how many seconds the machine will run until the execution is aborted.

result = tm.run("11010", timeout=5) # result = False

By default there’s no timeout limit, but if you specify this parameter and the time is exceeded during the run, the result will be None . If your machine is well designed and your input is not extremely big, runs should never take more than a second. If you set a timeout of a few seconds and your machine reaches the timeout, it’s very likely that you are under an infinite run.

The run method will only return decidability information, but it won’t return the machine state nor the content of the tapes. That information is stored in the attributes of the machine, so you can access them as follows:

state = tm.current_state # state = 'q1' tape_content = tm.tapes.words[0] # tape_content = ['1', '1', '0', '1', '0', '_']

For debugging purpuses you can also use the print_current_configuration method, which prints in a pretty format the actual configuration of the machine. For instance:

tm.print_current_configuration() 

The machine and the code used in this introduction guide can be found in the example1 folder.

In example2 folder you can find a code for automatic revision of students homeworks.

About

Turing machine implementation in Python

Источник

Машины Тьюринга в Python

Хотя у вас может не быть доступа к физической машине Тьюринга, это не должно помешать вам смоделировать машину Тьюринга с помощью… вашего компьютера! Я расскажу о том, как работают машины Тьюринга, и о коде Python, чтобы построить простую машину для проверки предполагаемых палиндромов. Я знаю, что программы, которые проверяют палиндромы, являются обычным упражнением для новичков в программировании, и что вы можете просто проверить их в Интернете или даже скопировать код на своем любимом языке. Однако давайте представим, что в глубине души вы действительно хотели бы использовать для этой задачи машину Тьюринга.

Эта статья вдохновлена ​​главой 5 книги Перспективы вычислений Роберта Героха — Amazon.

Что такое машина Тьюринга?

Машина Тьюринга состоит из трех частей:

Лента разделена на последовательность квадратов, в каждом из которых может храниться один символ, принадлежащий к данному набору символов.

Это не очень ответило

Чем интересны машины Тьюринга? Вы определенно уже слышали о них, поэтому давайте просто быстро скопируем это из собственных слов Тьюринга и оставим дальнейшие подробности в главе Героха, упомянутой выше.

Можно изобрести одну машину, которую можно использовать для вычисления любой вычислимой последовательности.

Машина Тьюринга может смоделировать что угодно, имея неограниченное пространство для хранения!

Как работают машины Тьюринга?

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

Когда машина закончила? Для этой цели зарезервировано специальное состояние. Как только машина входит в это состояние, программа завершает работу.

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

Реализация машины Тьюринга

Машина Тьюринга состоит из трех элементов (которые мы реализуем следующим образом):

1. состояние (строка с именем state )
2. записывающая головка (целое число с именем write_head )
3. лента (список с именем tape_list )

В качестве простой реализации напишем класс с этими элементами следующим образом:

Далее мы будем работать с таблицей правил, определенной в updateMachine .

Таблица правил

А таблица правил? Таблица, которую необходимо реализовать, приведена ниже — под ней следует пояснение.

Это требует некоторого объяснения! Начнем с определения состояний:

• q1 — исходное состояние. Здесь мы читаем символ n , который соответствует n-му символу в списке символов (при условии, что он не равен нулю). Эта информация «сохраняется» в состоянии при переходе в соответствующее состояние pn .
• pn — состояние после прочтения n-го символа изначально — теперь идем вправо и ищем конец строки, отмеченный нулем.
• rn — состояние после нахождения нуля в конце строки — теперь сравним последний символ строки. Если это палиндром, то он должен быть таким же, как n-й символ, который мы читаем в начале, и мы переходим в состояние q2 . в противном случае перейдите к состоянию qn, что означает «нет, это не палиндром».
• q2 — состояние после успешного сравнения последнего символа в строке — теперь идем влево и ищем начало строки, отмеченное нулем. Перезапустите цикл, перейдя к q1 .

Если вы запутались, некоторые примеры могут прояснить ситуацию. В таблицах ниже мы перечисляем ленту на каждом шаге (где положение записывающей головки подчеркнуто), а также состояние и char.

Во-первых, слово «из», которое не является палиндромом:

В последней строке, поскольку «f» не был 15-м символом алфавита (а именно «o», который мы считывали на первом шаге), машина переходит в состояние qn, правильно указывая, что «of» не является палиндром.

Во-вторых, символы «bbb», которые являются палиндромами:

Это было ужасно долго, но это сработало! Обратите внимание, что для переключения с p2 на r2 во второй раз при чтении нуля использовалось наше дополнительное условие * в таблице правил.

Или, что угодно, это работает.

Что касается кода, опять же, не усложняйте его и используйте операторы if и elif :

Настройка ввода/вывода

Нам по-прежнему нужен способ ввести строку в программу, а также установить начальное состояние машины, начальное положение записывающей головки и записать строку на ленту. Давайте сделаем все это сейчас:

Запуск кода

Наконец, давайте запустим код! Опять же, мы обманули и обращаемся к состоянию на каждой итерации, чтобы проверить, завершилась ли программа (состояние qn или qy). Однако вы легко можете представить себе печать на ленте специального символа для обозначения результата при желании (оставим это как «упражнение»). Создайте файл с именем test.py с содержимым:

> python test.py hello Checking: hello - - - q1 0 ['h', 'e', 'l', 'l', 'o', 0] p7 1 [0, 'e', 'l', 'l', 'o', 0] p7 2 [0, 'e', 'l', 'l', 'o', 0] p7 3 [0, 'e', 'l', 'l', 'o', 0] p7 4 [0, 'e', 'l', 'l', 'o', 0] p7 5 [0, 'e', 'l', 'l', 'o', 0] r7 4 [0, 'e', 'l', 'l', 'o', 0] qn 3 [0, 'e', 'l', 'l', 'o', 0] - - - hello is NOT a palindrome! Steps: 7

Checking: ooo - - - q1 0 ['o', 'o', 'o', 0] p14 1 [0, 'o', 'o', 0] p14 2 [0, 'o', 'o', 0] p14 3 [0, 'o', 'o', 0] r14 2 [0, 'o', 'o', 0] q2 1 [0, 'o', 0, 0] q2 0 [0, 'o', 0, 0] q1 1 [0, 'o', 0, 0] p14 2 [0, 0, 0, 0] r14 1 [0, 0, 0, 0] q2 0 [0, 0, 0, 0] q1 1 [0, 0, 0, 0] qy 2 [0, 0, 0, 0] - - - ooo is a palindrome! Steps: 12

Последние мысли

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

Источник

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Реализация машины Тьюринга на Python

AzaubaevViktor/TuringMachine

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Реализация машины Тьюринга на Python

Для работы в системе должен быть установлен Python 3.3. На более ранних версиях не тестировалось, поэтому правильная работа на версиях ниже не гарантируется. Как запускать программу на вашей системе, читайте в интернете.

Лента бесконечная в одну сторону.
Проверки на ошибки нет.
Память под память выделяется динамически — то есть ячеек может быть столко, на сколько хватит памяти компьютера.

Для начала работы программа попросит ввести имя файла с программой.
После этого вы должны ввести входные данные — натуральные неотрицательные числа через запятую.
Что значат надписи:

Выводится память от 0-й ячейки до 10-й
Каретка находится на ячейке памяти, куда указывает символ |, число после него — состояние МТ
Следующая строка — код, который будет выполняться.
В конце работы программа либо прерывается по ограничению по кол-ву шагов, либо по состоянию q0.
Выводится ответ.

Версия 1
Первая строка — версия стурктуры файла
Вторая строка — ограничение на кол-во шагов
# комментарий
q%номер_состояния% %состояние ячейки% -> q%номер_состояния% %состояние ячейки% [R/L/%ничего%] — команда.
Одна команда в одну строчку.

About

Реализация машины Тьюринга на Python

Источник