Машина тьюринга на python
Jupyter Widgets для реализации UI машины Тьюринга
Привет, Хабр! Хочу поделиться опытом в быстром создание интерфейса в Jupyter Notebook. Если у тебя есть какая-то задача, для которой нужен простой UI, и ты почему-то захотел сделать её в Юпитере, то добро пожаловать под кат.
Передо мной встала задача: реализовать наглядный интерфейс для машины Тьюринга. Наверное, самый простой вариант – реализовать это с помощью С# или Java для десктопа, а может даже на JS в браузере. Так как я занимаюсь датасаенсом и у меня юпитерголовногомозга – я решил делать с помощью Jupyter Widgets. На хабре я не нашел информации об этой технологии, нужно это исправлять. Пост подразумевает, что читатель уже знаком с языком Python и работал в Jupyter Notebook.
Jupyter Widgets
Jupyter Widgets – это интерактивные HTML-виджеты для Jupyter Notebook. Их прямое назначение – сделать ноутбук более динамичным, добавить в него различные элементы управления. У нас появляется возможность добавлять слайдеры, кнопки, прогресс бары и другие элементы в несколько строчек без знаний CSS. Как я вижу, основное применение этой технологии – быстрая разработка прототипов (особенно для ML-проектов) в которых нужен простой UI. Если вам нужно показать заказчику что-то интерактивное, а не просто таблицу или график, то первое, что я бы попробовал, — это виджеты в юпитере (ну а потом plotly и Dash). Более повседневный вариант использования для датасаентистов — удобная отладка с помощью функции interact.
Interact – наверное самая часто используемая функция этой библиотеки. Она создает слайдер и вызывает некоторую функцию (callback) при его изменении. Все это реализуется в одну строчку. Ему можно придумать массу полезных применений: например, можно смотреть, как ваша модель машинного обучения реагирует на изменение какого-то параметра или признака, просто двигая слайдер. Для примера я не стал импортировать xgboost, а просто построил график полинома, степень которого можно менять с помощью этого самого interact.
Машина Тьюринга
Машина Тьюринга – это расширение идеи конечного автомата, с помощью которого, теоретически, можно представить любой алгоритм. Она может быть формализована через алфавит, разрешенные состояния, входные символы, начальное состояние и функцию переходов. Основная часть машины — это лента с символами алфавита, которые последовательно обрабатываются движущейся влево и вправо считывающей головкой в соответствии с функцией переходов.
Пусть машина сейчас в состоянии «q1» и прочитан символ «A». Проводится проверка функции переходов, и если есть комбинация «q1 A», то мы знаем, в какое следующее состояние должен осуществиться переход, какой символ записывается в текущую позицию на ленте, и куда дальше двигается считывающая головка. Если такой комбинации («состояние-символ») нет, то работа машины завершается. Этих знаний должно быть достаточно, чтобы понять, что нужно отобразить в интерфейсе. Пример готового класса машины Тьюринга на питоне можно найти тут, я немного изменил его для своих нужд.
Для наглядности, рассмотрим следующую задачу. Дан массив из букв «А» и «В». Нужно сжать массив, удалив все буквы «В», но оставив буквы «А». Решение состоит в замене всех символов «В» на символ «*», а затем разбросанные в разных позициях буквы «А» следует сдвинуть вправо. Пример входа: «#BAABABA#». Выход для него: «####AAAA#». Здесь «#» — служебный пустой символ. Функция переходов под спойлером.
Визуализация
Прежде всего нужно понять, какие UI элементы должны отображаться.
Строки с текстом можно представить с помощью класса ipywidgets.HTML. Это виджет для отображения html, работа с ним выглядит так:
При изменение значения поля value, виджет автоматически перерисовывается. Три строки с текстом создадим с помощью трех разных html-виджетов.
Кнопки генерации строки и выполнения команды делаются с помощью ipywidgets.Button.
Слайдер представляется классом ipywidgets.IntSlider. Атрибутами можно передавать границы допустимых значений.
Обработка событий от UI-элементов происходит с помощью колбеков: функций, которые вызываются при возникновении событий. В нашем случае для кнопок нужно подписаться на событие клика, а для слайдера — на событие изменения значения элемента. Внутри этих колбеков будет происходить изменение значений html-виджетов.
Для отрисовки элементов можно передать их все в функцию display. Выводя все вместе, получим:
Все работает! На этом можно было бы остановиться, но согласитесь, выглядит довольно сумбурно. Попробуем это исправить.
Соберем контролы в более привычном виде. Перед каждой html строкой добавим лейбл, кнопки разместим в одну линию, вокруг этого сделаем красивую рамочку. Это можно сделать с помощью ipywidgets.Layout и ipywidgets.Box. Box – это контейнер, в который можно добавлять несколько виджетов в виде списка. Управлять отображением элементов внутри бокса легко с помощью атрибута layout. Благодаря технологии Flexbox из современного CSS можно красиво расположить элементы относительно друг друга. Здесь можно найти множество примеров, на основе которых достаточно просто собрать что-то свое. В итоге у меня получилось так:
Заключение
9. Turing Machine in Python
By Bernd Klein. Last modified: 07 Nov 2021.
Just to let you know straight-away: The Turing machine is not a machine. It is a mathematical model, which was formulated by the English mathematician Alan Turing in 1936. It’s a very simple model of a computer, yet it has the complete computing capability of a general purpose computer. The Turing machine (TM) serves two needs in theoretical computer science:
A Turing machine consists only of a few components: A tape on which data can be sequentially stored. The tape consists of fields, which are sequentially arranged. Each field can contain a character of a finite alphabet. This tape has no limits, it goes on infinitely in both directions. In a real machine, the tape would have to be large enough to contain all the data for the algorithm. A TM also contains a head moving in both directions over the tape. This head can read and write one character from the field over which the head resides. The Turing machine is at every moment in a certain state, one of a finite number of states. A Turing program is a list of transitions, which determine for a given state and character («under» the head) a new state, a character which has to be written into the field under the head and a movement direction for the head, i.e. either left, right or static (motionless).
Formal Definition of a Turing machine
A deterministic Turing machine can be defined as a 7-tuple
Example: Binary Complement function
Let’s define a Turing machine, which complements a binary input on the tape, i.e. an input «1100111» e.g. will be turned into «0011000».
Σ = <0, 1>
Q =
q 0 = init
q f = final
| Function Definition | Description |
|---|---|
| δ(init,0) = (init, 1, R) | If the machine is in state «init» and a 0 is read by the head, a 1 will be written, the state will change to «init» (so actually, it will not change) and the head will be moved one field to the right. |
| δ(init,1) = (init, 0, R) | If the machine is in state «init» and a 1 is read by the head, a 0 will be written, the state will change to «init» (so actually, it will not change) and the head will be moved one field to the right. |
| δ(init,b) = (final, b, N) | If a blank («b»), defining the end of the input string, is read, the TM reaches the final state «final» and halts. |
Implementation of a Turing machine in Python
We implement a Turing Machine in Python as a class. We define another class for the read/write tape of the Turing Machine. The core of the tape inside the class Tape is a dictionary, which contains the entries of the tape. This way, we can have negative indices. A Python list is not a convenient data structure, because Python lists are bounded on one side, i.e. bounded by 0.
We define the method str(self) for the class Tape. str(self) is called by the built-in str() function. The print function uses also the str function to calculate the «informal» string representation of an object, in our case the tape of the TM. The method get_tape() of our class TuringMachine makes use of the str representation returned by str.
sandipanweb
Simply Data Science
Simulating a Turing Machine with Python and executing programs on it
In this article, we shall implement a basic version of a Turing Machine in python and write a few simple programs to execute them on the Turing machine. This article is inspired by the edX / MITx course Paradox and Infinity and few of the programs to be executed on the (simulated) Turing machine are taken from the course. Also, some programs are from this Cambridge tutorial.
A few Definitions
Let’s start by defining a Turing machine (originally invented by Alan Turing) formally, as is shown in the following figure:
The python implementation for simulating a Turing Machine
The following python code shows a very simple implementation of a Turing machine. It accepts a program as a string, with each transition function defined on a new line. The state halt is denoted by H.
In the next section we shall show how a program on this Turing Machine will look like and how to run such a program, by instantiating the above class. We shall demonstrate with a few programs.
1. Binary Addition with Turing Machine
The following figure shows how to perform binary addition with a Turing machine, where the binary numbers to be added are input to the Turing machine and are separated by a single blank. The TM header is assumed to be positioned at the leftmost position of the first number, in the very beginning.
0 0 0 r 0
0 1 1 r 0
0 _ _ r 1
1 0 0 r 1
1 1 1 r 1
1 _ _ l 2
2 0 1 l 2
2 1 0 l 3
2 _ _ r 5
3 0 0 l 3
3 1 1 l 3
3 _ _ l 4
4 0 1 r 0
4 1 0 l 4
4 _ 1 r 0
5 1 _ r 5
5 _ _ * H
Given the two binary numbers, the Turing Machine
till the second number becomes 0.
The following code shows how the above program can be run to add two input binary numbers 1101 (decimal 13) and 101 (decimal 5) to output the binary number 10010 (decimal 18). The final state of the machine is H (halt), as expected.
The following animation shows how the binary numbers are added using the TM simulator.
2. Converting a Binary to a Unary number with TM
Let’s assume the TM tape contains a binary representation of a number n ( n > 0 ) as a sequence of zeros and ones, and is otherwise blank. The reader positioned at the left-most member of the sequence. The following figure shows the program that replaces the original sequence with a sequence of n ones, where the original sequence names n in binary notation:
The following animation shows the result of running the program on the TM simulator, with the input 1010, the output obtained is a sequence of 10 ones.
3. Converting a Unary to a Binary number with TM
Let’s assume the TM tape contains a sequence of n ones ( n > 0 ) and is otherwise blank. The reader positioned at the left-most member of the sequence. The following TM program replaces the sequence of n ones, with a sequence of zeroes and ones that names n in binary notation:
The following animation shows the result of running the program on the TM simulator, with the input 11111111111 (eleven ones), the output obtained is the binary representation of 11.
4. Doubling the length of a sequence with TM
The following figure shows the program to be run to double the length of a sequence of ones, input to the TM
The following animation shows the result of running the program on the TM simulator, starting with five ones as input, obtaining ten ones on the tape as output.
5. Simulating the 4-state Busy Beaver with TM
The following figure shows the program to be run
The following animation shows the result of running the program on the TM simulator, as expected it outputs 13 ones on the tapes and halts in 107 steps. 
6. Detecting a Palindrome with TM
The following program checks a string of symbols on the tape and returns a 1 if it is a palindrome and a 0 if it is not.
The following animation shows the result of running the program on the TM simulator with a palindrome.
The following animation shows the result of running the program on the TM simulator with a non-palindrome.
Доказательство Тьюринг-полноты однострочников на Python
Немного теории
Чёткие правила данного автомата изложены в Википедии по ссылке здесь.
Вкратце, мы имеем бесконечную ленту из последовательно размещённых клеток, которые могут иметь только два состояния (0 и 1), будущее состояние клетки зависит от текущих значений трёх клеток — её самой и двух её ближайших соседей и рассчитывается по определённому несложному алгоритму.
Получается, что если мы сможем написать в одну строчку этот клеточный автомат, значит и любой другой алгоритм написать в одну строчку тоже будет возможно.
Реализация
Сразу уточню, что символ «;» я считал началом новой строки, чем он по сути и является, иначе задача превращается в тривиальную.
Итак, опредилившись с тем что же именно я собираюсь написать, я, недолго думая, запустил VSCode и. И завис. Потому что неясно было что писать. Ясно было, что нужен цикл while, ввод начального состояния, которое нужно как-то обработать, действия над ним в цикле, Кроме того, цикл надо ещё как-то остановливать, если состояние системы стабилизировалось и больше не меняется.
Как это всё уместить в одну строчку, было не очень понятно. Например даже результат вызова input() нельзя никак занести в обычную в переменную и потом работать с ним дальше одной строкой.
Итоговый код и как он работает
Итак, нам необходимо каждый проход цикла проверять состояние системы и заканчивать выполнение программы, если оно такое же, как предыдущее(состояние стабилизировалось).
Сперва, мы должны запросить на вход начальное состояние, причем сделать это лишь один раз. Также мы будем сравнивать текущее состояние системы с предыдущим. Для этого используем следующий код:
Далее, уже в теле цикла мы объявляем фиктивную переменную a которой присваиваем значение длинного длинного сравнения через оператор or. На самом деле, оператор сравнения здесь нужен чтобы выполнить большое количество исполняемого кода, в котром каждая вызываемая функция вернёт None. Возможно, можно было реализовать подобное более красиво, но это самое быстрое рабочее решение, которое пришло мне в голову.
В полном же варианте нарощенном на данный скелет мы обновляем l (предыдущее состояние), проходим один цикл клеточного автомата, перезаписывая переменную s, и выводим новое состояние.
Вот так выглядит финальный код.
Правда, скорее всего, код получится слегка нечитаемым да и дебаггинг будет затруднён. )
Автор знаком с python на любительском уровне и не пишет на нём ничего серьёзного, поэтому прошу простить, если проглядел какие-то очевидные вещи и возможности. Автор понимает, что написание подобного кода в реальном проекте, чревато некоторым непониманием со стороны коллег и не призывает никого повторять изложенные здесь эксперименты)
Машина тьюринга на python
Emulator of turing machine and markov algorithm.
Установка программы производится через пакетный менеджер pip. Получить последнюю версию можно командой (попробуйте добавить sudo в начало команды, если установка не проходит успешно):
После этого программа переходит в режим считывания и на каждую введенную строку печатает результат работы алгоритма. Если программа перестала отвечать на запросы, вероятнее всего, алгоритм зациклился на введенной строке. Нажмите ctrl+C для остановки выполнения.
Ограничения: в НАМ пробельные символы игнорируются, МТ не работает для пустых строчек.
Также программа может работать в режиме компилятора и перерабатывать формальное описание алгоритма в программу на Python.
Скомпилированный файл преобразовывает каждую строчку со входного потока и выдает результат в выходной. Если алгоритм не применим (не останавливается) к данной строчке, то вторая команда будет выполняться вечно или упадет с ошибкой.
Взаимодействие с системой ejudge
Для установки в систему ejudge:
Краткие теоретические сведения
Машина Тьюринга (МТ) — абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
Машина Тьюринга, согласно тезису Чёрча — Тьюринга, способна имитировать все исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
В состав машины Тьюринга входит неограниченная в обе стороны лента, разделённая на ячейки, и управляющее устройство (также называется головкой записи-чтения (ГЗЧ)), способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.
Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.
Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм, реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Одно из состояний машины Тьюринга помечено как заключительное, и переход в него означает конец работы, остановку алгоритма.
Для каждой возможной конфигурации q[i],a[j] имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.
В начале МТ ищет правую границу входного слова, а затем пишет a в пустую ячейку и останавливается.