Полная по тьюрингу машина

Содержание

Тьюринг-полнота

Содержание

Введение [ править ]

Определение:

Вычислительное устройство является Тьюринг-эквивалентным (англ. Turing-equivalent), если оно может эмулировать машину Тьюринга.

Определение:

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

Зачастую Тьюринг-эквивалентные языки программирования называют Тьюринг-полными.

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

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

На практике полнота по Тьюрингу похожа на идеализацию. Компьютеры имеют ограниченное количество памяти, а неограниченная по времени их работа может быть прервана физическим воздействием (выключение, поломка), что как бы ограничивает число задач, которые они могут решить. На самом деле, физические ограничения в контексте Тьюринг-полноты не берутся во внимание: Тьюринг-полный исполнитель не должен быть ограничен по времени и памяти лишь самим исполнителем.

Критерии Тьюринг-полноты [ править ]

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

Тьюринг-полнота и неполнота некоторых языков программирования [ править ]

Доказать Тьюринг-полноту языка программирования можно, предложив способ реализации машины Тьюринга на этом языке. Кроме того, можно предложить на нём интерпретатор Тьюринг-полного языка.

Assembly language [ править ]

Язык Ассемблера достаточно примитивен относительно языков программирования высокого уровня: он рассчитан на архитектуру с конечной памятью и работает с конечным набором регистров. Однако, не был бы он полным по Тьюрингу, не были бы Тьюринг-полны и любые высокоуровневые языки программирования.

Всё необходимое для машины Тьюринга на asm можно сделать примерно так:

И далее использовать инструкцию [math]\mathrm[/math] или ей подобную, чтобы выполнять определённую последовательность команд при определённом текущем значении, таким образом обеспечив ветвление.

Pascal [ править ]

C [ править ]

В языке C нет высокоуровневого понятия переменной (в смысле Паскаля), есть объекты (object), хранящиеся в памяти как последовательно расположенные байты,имеющие адрес (байты в свою очередь состоят из неадресуемых битов). Целые типы ограничены (конечное множество значений), указатель отождествляется с адресом, постулируется возможность хранить адрес в целочисленной переменной (int или long — зависит от реализации), откуда следует ограниченность множества значений указателей, а стало быть, и ограниченность адресного пространства C-машины. То есть язык C, как и язык ассемблера, ориентирован на архитектуру с конечной памятью. Файл не является типом данных языка C, в отличие от Паскаля. Это вещь из окружения, для работы с которой есть операции над потоками в виде набора библиотечных функций. Тип fpos_t, принятый в стандарте C для позиционирования файлов, постулируется как «отличный от массива тип данных (object type)». Следовательно, множество значений этого типа конечно, а значит, максимальная длина файла в языке C ограничена сверху.

SQL [ править ]

HTML [ править ]

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

Некоторые другие ЯП [ править ]

Название языка	Год изобретения	Парадигма	Уровень	Зависимость от архитектуры процессора	Полнота по Тьюрингу
C	1972	Процедурный	Низкий	зав. от ISO	Да
C++	1983	Мультипарадигменный	Высокий/Низкий	Нет	Да
Язык Ассемблера	1950	Полнофункциональный	Низкий	Да	Да
SQL	1989	Декларативный	Высокий	Нет	Нет
Haskell	1990	Функциональный	Высокий	Нет	Да
HTML	1986	Декларативный	Высокий	Нет	Нет
CSS	1996	Декларативный	Высокий	Нет	Нет
Java	1995	Объектно-ориентированный	Высокий	Нет	Да
JavaScript	1995	Объектно-ориентированный	Высокий	Нет	Да
Python	1991	Объектно-ориентированный	Высокий	Нет	Да
XML	1998	Декларативный	Высокий	Нет	Нет
Brainfuck	1993	Эзотерический	Низкий	Да	Да
Whitespace	2003	Эзотерический	Низкий	Да	Да

Интересные случаи полноты по Тьюрингу [ править ]

Шаблоны C++ [ править ]

Java Generics [ править ]

URISC [ править ]

URISC (от англ. Ultimate RISC) — предельный случай процессора типа RISC (буквально: компьютер с предельно сокращённым набором инструкций), который умеет выполнять одну-единственную инструкцию. Обычно это «вычесть и пропустить следующую инструкцию, если вычитаемое было больше уменьшаемого» (англ. «reverse-subtract and skip if borrow»). Аналогичная концепция, основанная именно на «вычесть и перейти, если результат не положительный» (англ. «subtract and branch unless positive»), называется SUBLEQ.

URISC также известен в современной литературе как OISC (англ. One Instruction Set Computer) и является полным по Тьюрингу.

mov [ править ]

Источник

Наследие Тьюринга: машина, тест и полнота

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

Для того, чтобы представить простейшую машину Тьюринга, взглянем на её художественную реализацию:

Это бесконечная лента, не имеющая ни начала, ни конца, поделённая на ячейки. Для работы с ней мы используем некое управляющее устройство (автомат), для визуализации выбрана каретка. В каждый момент времени она имеет состояние qj и считывает содержимое ячейки ai. О том, что происходит в остальной части ленты, каретка не знает, соответственно оперировать она может только текущими данными. Всего возможно три типа действий, зависящий от этой композиции:

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

Создадим таблицу для реализации алгоритма Тьюринга:

Символами _Л, _П, _Н обозначим направление движения автомата – соответственно сдвиг «влево», «вправо» или неподвижное положение.

Пусть наша лента выглядит так:

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

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

Зачем это программисту

Машина Тьюринга позволяет размять мозги и взглянуть на решение задачи иначе. В конечном счёте, с той же целью следует познакомиться с:

Но машина Тьюринга – базовая теория алгоритмов, которая помогает думать не столько о средствах языка, сколько о различных путях решения задачи. Для профессионального роста – это необходимый навык.

Полнота по Тьюрингу

Ещё один важный вопрос, связанный с именем известного математика. На форумах и в статьях вы неоднократно могли видеть выражение «полный\не полный язык программирования по Тьюрингу». Ответ на вопрос «что это означает?» возвращает нас к описанной выше теории. Как уже было сказано, машина Тьюринга позволяет выполнить любое преобразование, соответственно, вы можете реализовать на ней абсолютно любой алгоритм или функцию. То же самое относится и к языкам. Если с его помощью вы можете реализовать любой заданный алгоритм – он тьюринг-полный. Если в дело вступают ограничения синтаксиса или любые физические – не полный.

Тест по Тьюрингу

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

Такой тест на долгие годы предопределил развитие ИИ – программы вроде Элизы или PARRY строились именно на копировании человеческого поведения машиной. Уже позднее, когда стало понятно, что путь тупиковый, вектор развития был сдвинут в сторону изучения механизмов интеллекта. Однако до сих пор тема «способна ли мыслить машина» лежит в основе многих тестов, романов и кинофильмов.

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

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

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

Для того, чтобы представить простейшую машину Тьюринга, взглянем на её художественную реализацию:

Создадим таблицу для реализации алгоритма Тьюринга:

Пусть наша лента выглядит так:

Зачем это программисту

Полнота по Тьюрингу

Тест по Тьюрингу

Источник

Тьюринг-полнота Generic типов Java

Периодически на хабре можно встретить статьи о том, какие невероятные вещи можно сделать на шаблонах C++: конечные автоматы, лямбда-исчисление, машина Тьюринга и многое другое.

Параметризованные типы в Java традиционно считаются лишь пародией на шаблоны C++ (несмотря на то, что их даже сравнивать как-то некорректно), и причины этого несложно понять. Тем не менее не всё так плохо, и компилятор Java можно заставить производить во время проверки типов любые вычисления, лишь бы хватило оперативной памяти. Конкретный способ это сделать был описан в ноябре 2016-го года в этой прекрасной публикации. Его я и хотел бы объяснить.

Для затравки приведу следующий код. Корректен ли он? Предлагаю скомпилировать и проверить, угадали ли вы результат.

Компилятор выбросит java.lang.StackOverflowError независимо от размера стэка.

Разберёмся, почему компилятор ведёт себя именно так (я бы не назвал это багом), как понимание данных причин может быть полезно и причём тут машина Тьюринга.

1. О ковариантности и контравариантности

В первую очередь поговорим об основах. Самый простой способ использования параметризованных типов выглядит примерно так:

Сосредоточимся на контравариантных типах.

2. Формализация подмножества контравариантных типов

Итак, определим, какие именно типы в Java нас интересуют. Введём понятие индуктивно:

Теперь можно наконец ввести отношение является подтипом ««.

В этом месте появляется существенное ограничение. Чтобы отношение совпадало со стандартным способом определения подтипов в Java, необходимо, чтобы в пункте 2 значение n было нечётным.

Полного формального доказательства я приводить не буду, оно было бы неуместно длинным. Правильнее будет рассмотреть ситуацию на примерах.

n=3:
interface S extends C1 >> <>
Докажем, что верно :

Given a generic type declaration $» data-tex=»inline»/> (n > 0), the direct supertypes of the parameterized type $» data-tex=»inline»/> where at least one of the is a wildcard type argument, are the direct supertypes of the parameterized type $» data-tex=»inline»/> which is the result of applying capture conversion to $» data-tex=»inline»/> (§5.1.10)

n=2:
interface S extends C1 > <>
Предположим, что :

Случаи n>2 рассматриваются аналогичным образом.

Теперь можно сформулировать следующую теорему, которая позже будет доказана:

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

Другими словами, в общем случае в Java невозможно определить, является ли один тип подтипом другого.

3. Что будем понимать под машиной Тьюринга

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

Конфигурация машины Тьюринга — это четвёрка , в которой — это текущее состояние, — это левая часть ленты, — это текущий символ и — это правая часть ленты.

Шаг выполнения машины отображает множество конфигураций само в себя следующим образом:

Так же учитываются граничные случаи (символ здесь означает пустую строку). Они показывают, что по достижении конца строки (слева или справа) к ней автоматически дописывается символ :

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

4. Subtyping Machines

Начнём связывать воедино имеющиеся у нас понятия. Цель — сопоставить шаги выполнения машины Тьюринга с процессом проверки типов в Java. Положим, что у нас есть такой запрос:

Это утверждение, истинность или ложность которого предлагается доказать. Для удобства введём две альтернативные формы записи:

— это специальная конфигурация, называемая завершающей (halting).
Отметим, что имея правило наследования и подставляя тип , мы получаем следующее правило выполнения:

Так же в силу контравариантности используемых типов справедливо такое правило:

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

Как видно, проверка типов зацикливается, этим и обусловлено переполнение стэка во время компиляции. В общем виде описанный процесс можно выразить таким образом:

Выражение истинно тогда и только тогда, когда существует завершающийся процесс выполнения .

Пример посложнее

Рассмотрим следующую таблицу классов:

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

5. Построение машины Тьюринга

Имея машину Тьюринга и входную ленту , построим типы и таким образом, что тогда и только тогда, когда останавливается на входе .
Для каждого состояния введём 6 классов: , , , , и ; для каждого символа построим класс . Символ из определения машины Тьюринга для удобства будем записывать как , ему будет соответствовать класс . Так же дополнительно введём 4 класса: , , и .

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

и — это по сути типы и из последнего примера. Большую часть времени они блуждают (wander) вдоль ленты. Смысл типов и тоже сохраняется: они нужны для разворота на конце ленты. Единственное исключение — момент, когда ( это или ) встречается с соответствующим ему : он при этом «превращается» в . — класс для завершающего состояния, обрабатываемый особым образом.
Полное описание выглядит так:

и указывают машине, что пришло время для очередного шага выполнения. Соответственно, для каждого правила в машине Тьюринга мы строим специальное отношение наследования. При этом не забываем об особых правилах работы с классом :

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

Остальные 9 случаев расписываются аналогичным образом.

6. Fluent interface

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

Для этого напишем следующий класс:

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

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

7. Безопасный Builder

Итак, я хочу иметь следующий код, который мог бы валидироваться компилятором:

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

Довольно-таки прямолинейно. Машина остановится только на входе .

Классы User и UserBuilder реализованы следующим образом (осталось только заполнить многоточия):

Осталось только обеспечить требуемое предположение;

Целиком пример можно найти на гитхабе.

Чтобы не быть голословным, далее я привожу пример машины Тьюринга посложнее. Такая машина, грубо говоря, проверяет парность скобок, т.е. выражение ()(()()) является валидным, а выражение ()())(() — невалидным. Только открывающая и закрывающая скобки заменены символами A и B ( x — дополнительный символ, означающий, что скобка на этом месте уже проверена).
Функция перехода будет следующей:

Поиграться с данной машиной, или погенерировать свои, можно всё там же на гитхабе.
Да, генератор кода по описанию машины Тьюринга присутствует.

Для данной грамматики следующий код спокойно скомпилируется:

а вот этот уже нет:

8. Заключение

Содержательная часть на этом закончена. Мы узнали, как можно заставить компилятор валидировать цепочки вызовов согласно произвольному заранее заданному алгоритму.

Но можно — не значит нужно.
Во-первых, слишком много дополнительно объявленных классов, да и сигнатуры методов класса Builder выглядят очень сложно.
Во-вторых, компилятору понадобится гораздо больше памяти, чтобы не падать на сложных выражениях. В первую очередь — гораздо более глубокий стэк.
В-третьих, сложная диагностика ошибок. Типичный вывод компилятора выглядит как-то так (для краткости стёр названия пакетов):

Уровень информативности нулевой. Если хочется найти ошибку, то остаётся только два варианта:

Тогда зачем это всё? Ответов, опять же, несколько:

Разработчики Kotlin, к примеру, знали, что в Java легко составить типы, проверка которых приведёт к экспоненциально долгому времени компиляции, и ввели т.н. Non-Expansive Inheritance Restriction. Поясню на минимальном примере:

Цель проста — избежать «слишком сложных» типов, тем самым гарантируя высокую скорость компиляции. Из-за данного ограничения описанный способ запуска машин Тьюринга на Kotlin реализовать невозможно. В таком случае есть шанс, что проверка типов в Kotlin гарантированно завершается за конечное время.

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

Источник