Что такое полнота языка по тьюрингу

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

Содержание

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

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

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

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

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

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

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

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

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

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++ [ править ]

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 [ править ]

Источник

Неожиданная полнота по Тьюрингу повсюду

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

Любая достаточно сложная программа на Си или Фортране содержит заново написанную, неспецифицированную, глючную и медленную реализацию половины языка Common Lisp. — Десятое правило Гринспена

Полнота по Тьюрингу (Turing-completeness, TC) — это свойство системы при некотором простом представлении ввода и вывода реализовать любую вычислимую функцию.

Тьюринг-полнота — фундаментальное понятие в информатике. Она помогает ответить на многие ключевые вопросы, например, почему невозможно создание идеальной антивирусной программы. Но в то же время она является поразительно распространённым явлением. Казалось бы, компьютерной системе трудно достичь такой универсальности, чтобы выполнять любую программу, но получается наоборот: трудно написать полезную систему, которая немедленно не обратится в полную по Тьюрингу. Оказывается, что даже небольшой контроль над входными данными и преобразованием их в результат, как правило, позволяет создать тьюринг-полную систему. Это может быть забавным, полезным (хотя обычно нет), вредным или чрезвычайно небезопасным и настоящим подарком для хакера (см. о «теоретико-языковой безопасности», которая изучает методы взлома «странных машин» 1 ). Удивительные примеры такого поведения напоминают нам о том, что полнота по Тьюрингу таится повсюду, а защитить систему чрезвычайно сложно.

«Слишком мощные» языки программирования тоже могут спровоцировать неприятные DoS-атаки. Фаззер afl нашёл в OpenBSD такой roff, что способен на генерацию бесконечного цикла, злоупотребляя некоторыми правилами подстановки строк.

Многие конфигурации, специальные языки, инструменты или сложные игры, как выясняется, нарушают правило наименьшей власти и «случайно становятся полными по Тьюрингу», как шаблоны MediaWiki, sed или многократное повторение команд regexp/find-replace в редакторе. Вообще, любая форма замены строк или шаблонирования, или компиляции на лету с высокой вероятностью является тьюринг-полной системой сама или при повторении, так как они часто поддерживают лямбда-исчисление или переписывание термов языка или метки, например, эзотерические языки «///» или Thue.

С другой стороны, направление исследований компьютерной безопасности под названием «странные машины» (weird machines) часто выявляет поистине поразительные тьюринг-полные системы. Причём у разных людей они вызывают удивление в разной степени: одним кажется необычным то, что других не удивляет.

См. также

Ссылки

Приложение

Сколько компьютеров в вашем компьютере?

Некоторые увязают в спорах о странных машинах или о том, насколько «большим» станет агент ИИ: будет создан один такой, два, десять или миллионы. Неважно, поскольку это просто организационный вопрос. На самом деле важны входы и выходы системы: насколько работоспособна система в целом и какие ресурсы потребляет? Никого не волнует, если Google работает на 50 суперкомпьютерах, 50 000 мейнфреймах, 5 миллионах серверов, 50 млн встроенных/мобильных процессоров или на сочетании всего перечисленного. Неважно, что Google использует разнообразные чипы: от самодельных «тензорных процессоров» до уникальных кремниевых процессоров (Intel реализует их на чипах на процессоры Xeon для ряда крупнейших клиентов), FPGA, GPU, CPU до ещё более экзотического оборудования вроде квантовых компьютеров D-Wave. Важно только, чтобы она сохраняла конкурентоспособность и могла предоставлять услуги за умеренную плату. В конце концов, сегодня суперкомпьютер выглядит обычно как большое количество серверов в стойках с огромным количеством GPU и необычно высокоскоростными соединениями InfiniBand. То есть суперкомпьютер не так уж сильно отличается от дата-центра, как можно подумать. Любое из перечисленного оборудования может поддерживать многочисленные странные машины в зависимости от своей внутренней динамики и связности.

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

Вот пример плохо определённого вопроса: сколько компьютеров сейчас у вас в карманах и на столе? Сколько компьютеров в вашем «компьютере»? Думаете, только один? Давайте посмотрим внимательнее.

Речь идёт не только о CPU: в наше время транзисторы и процессорные ядра настолько дёшевы, что теперь часто имеет смысл выделять отдельные ядра на задачи реального времени, для повышения производительности, для безопасности, чтобы избежать нагрузки на основную ОС, для совместимости со старой архитектурой или существующего программным пакетом. Просто потому что DSP или ядро быстрее запрограммировать, чем создать специализированный ASIC, или потому что это самое простое из возможных решений. Кроме того, многие из этих компонентов могут использоваться в качестве вычислительных элементов, даже если они не предназначены или вообще скрывают эту функциональность.

«Удивительно, как много разнородных ядер процессора интегрированы в Intel Silvermont Moorefield SoC (ANN): x86, ARC, LMT, 8051, Audio DSP, каждый на своей прошивке и с поддержкой интерфейса JTAG

Здесь нет ничего необычного в историческом контексте, ведь даже самые первые мейнфреймы обычно включали в себя несколько компьютеров, где основной компьютер выполняет пакетную обработку, о вспомогательные компьютеры обеспечивают высокоскоростные операции ввода/вывода, которые в противном случае помешают основной машине своими прерываниями.

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

1. Активная область исследований — создание языков и систем, которые тщательно спроектированы и гарантированно не являются тьюринг-полными (например. тотально функциональное программирование). Зачем прилагать столько усилий для создания языка, на котором невозможно написать многие программы? Дело в том, что полнота по Тьюрингу тесно связана с теоремой Гёделя о неполноте и теоремой Райса. Поэтому если разрешить TC, то мы теряем всевозможные свойства доказуемости. Наоборот, в не полном по Тьюрингу языке легко доказываются разные полезные вещи: например, что программа завершена, типобезопасная она или нет, что её легко преобразовать в логическую теорему, что она потребляет ограниченное количество ресурсов, что реализация протокола верна или эквивалентна другой реализации. Легко доказывается отсутствие побочных эффектов и что программу можно преобразовать в логически эквивалентный, но более быстрый вариант (это особенно важно для декларативных языков вроде SQL, где способность оптимизатора преобразовать запросы — ключ к приемлемой производительности. Хотя, конечно, на SQL можно делать удивительные вещи, такие как градиентный спуск для моделей машинного обучения, а некоторые расширения SQL делают его тьюринг-полным в любом случае, позволяя либо закодировать циклическую систему тегов, либо model DSL, либо вызвать PL/SQL и т.д.

Вот некоторая литература о странных машинах:

2. Хотя линейные нейросети эксплуатируют режим плавающей точкой с округлением до нуля для кодирования потенциально тьюринг-полного поведения (для RNN), но это незаметно в нормальной работе, что одновременно является случайным тьюринг-полным поведением и наглядным примером безопасного языка. ↑

3. Dwarf Fortress даёт часовые механизмы, поэтому полнота по Тьюрингу неудивительна. Но и вода реализована как простой клеточный автомат, поэтому есть даже больше способов получить тьюринг-полноту! Сейчас игровая вики называет четыре потенциальных способа создания логических вентилей: жидкости, механизмы часового механизма, минные тележки и логические вентили существ/животных с участием дверей и датчиков давления. ↑

4. Полная спецификация PDF исключительно раздута. Например, в простой программе просмотра PDF с поддержкой достаточного количества спецификации PDF, как браузер Google Chrome, можно играть в Breakout (потому что PDF включает собственное странное подмножество JavaScript). Официальная программа просмотра Adobe PDF поддерживает функциональность вплоть до трёхмерного САПР. ↑

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник