Полный по Тьюрингу
В информатике и в логике , формальная система называется полной в смысле Тьюринга или Тьюрингу (за слоем английского Тьюринг-полной ) , если он имеет выразительную силу , по крайней мере , такой же, машин Тьюринга . Таким образом, в такой системе можно запрограммировать любую машину Тьюринга.
Это понятие актуализируется тезисом Чёрча , который постулирует существование естественного понятия вычислимости. Таким образом, выразительная сила машин Тьюринга совпадает с мощью рекурсивных функций , лямбда-исчисления или даже счетных машин .
Хотя определенные модели вычислений, называемые гиперкомпьютерами , строго более выразительны, чем машины Тьюринга, эти модели являются объектами спекуляций (требующих, например, выполнения бесконечного числа операций или вычислений на множестве чисел. Реальных), и это не так. известно, осуществимы ли они физически. В этих условиях тезис Чёрча предполагает универсальность вычислительной модели машины Тьюринга: любая полная по Тьюрингу система фактически была бы эквивалентна машинам Тьюринга.
Резюме
- 1 полные по Тьюрингу языки программирования
- 2 языка, не являющихся полными по Тьюрингу
- 3 Примеры вне языков программирования
- 4 Статьи по теме
- 5 Примечания и ссылки
- 5.1 Примечания
- 5.2 Ссылки
- 6.1 Связанные статьи
Полные по Тьюрингу языки программирования
Подобно вычислительной модели, компьютерный язык называется полным по Тьюрингу, если он позволяет представить все вычислимые функции в смысле Тьюринга и Черча (несмотря на ограниченность компьютерной памяти).
Некоторые авторы используют это свойство для определения языка программирования , но можно выбрать и другие определения.
Обычные языки программирования ( C , Java …) являются полными по Тьюрингу, потому что в них есть все ингредиенты, необходимые для моделирования универсальной машины Тьюринга (подсчет, сравнение, чтение, запись и т. Д.). Язык C ++ также является полным по Тьюрингу, и подмножество, допускающее универсальное программирование ( шаблоны ), также .
Язык SQL , изначально неполный в смысле Тьюринга, стал таковым со стандартом SQL: 1999, позволяющим писать рекурсивные запросы .
Язык LaTeX (от TeX ), предназначенный для компоновки документов, также является полным по Тьюрингу.
Сам по себе язык HTML не является полным по Тьюрингу, хотя было доказано, что язык CSS (версия 3) позволяет построить код 110 элементарного клеточного автомата (см. Правило 110 (in) ), известный как универсальный в смысле Тьюринга. . Эти два языка часто неразделимы, мы можем сделать вывод, что HTML + CSS является полным по Тьюрингу, и поэтому эта ассоциация теоретически делает его языком программирования.
Полный по Тьюрингу язык наследует характеристики машины Тьюринга. Например, проблема отключения является неразрешимой , так что невозможно написать программу , которая говорит ли заканчивается произвольная программа дано ему или нет.
Языки, не являющиеся полными по Тьюрингу
Некоторые языки, предназначенные для решения конкретных проблем, не являются полными по Тьюрингу. Система F , формализм лямбда-исчисления является примером. Более того, по замыслу тотальные языки (en) , на которых все вычисления обязательно заканчиваются (как язык Галлина помощника по доказательству Coq ), также не являются полными по Тьюрингу. Однако последние на практике способны просчитать все, что интересует, то есть могут реализовать все функции, которые могут нам понадобиться в практической жизни; вычисления, которые ускользают от них, либо имеют сложность за пределами воображаемого и реализуемого, либо не заканчиваются. Затем компиляция должна продемонстрировать завершение программ или потребовать взаимодействия с программистом для некоторых демонстраций, но это цена, которую приходится платить за качество кода, правильное по конструкции.
Примеры вне языков программирования
Некоторые игры и программное обеспечение являются полными по Тьюрингу случайно, даже если их авторы этого не хотят и не задумываются:
Статьи по Теме
- Бесконечная петля
- Теорема Райса
- Теория вычислимости
- Церковный тезис
Полнота по Тьюрингу
В теории вычислимости система правил манипулирования данными (например, набор команд компьютера , язык программирования или клеточный автомат ) называется полной по Тьюрингу или универсальной в вычислительном отношении, если ее можно использовать для моделирования любой машины Тьюринга . Это означает, что эта система способна распознавать или определять другие наборы правил обработки данных. Полнота по Тьюрингу используется как способ выразить мощь такого набора правил манипулирования данными. Практически все языки программирования сегодня являются полными по Тьюрингу. Концепция названа в честь английского математика и программиста Алана Тьюринга .
Связанная концепция — это концепция эквивалентности Тьюринга — два компьютера P и Q называются эквивалентными, если P может моделировать Q, а Q может моделировать P. Тезис Черча – Тьюринга предполагает, что любая функция, значения которой могут быть вычислены с помощью алгоритма, может быть вычислена с помощью Машина Тьюринга, и, следовательно, если какой-либо реальный компьютер может моделировать машину Тьюринга, это эквивалент машины Тьюринга. Универсальная машина Тьюринга может быть использована для имитации любой машины Тьюринга и выдвижением вычислительных аспектов любого возможного реального компьютера. [NB 1]
Чтобы показать, что что-то является полным по Тьюрингу, достаточно показать, что это может быть использовано для моделирования некоторой полной системы по Тьюрингу. Например, императивный язык является полным по Тьюрингу, если он имеет условное ветвление (например, операторы «if» и «goto» или инструкция « переход при нулевом значении»; см. Компьютер с одним набором инструкций ) и возможность изменять произвольные объем памяти (например, возможность поддерживать произвольное количество элементов данных). Конечно, никакая физическая система не может иметь бесконечную память; но если игнорировать ограничение конечной памяти, большинство языков программирования в остальном являются полными по Тьюрингу.
В разговорной речи термины «полный по Тьюрингу» и «эквивалент по Тьюрингу» используются для обозначения того, что любой реальный компьютер общего назначения или компьютерный язык может приблизительно имитировать вычислительные аспекты любого другого реального компьютера общего назначения или компьютерный язык.
Реальные компьютеры, сконструированные до сих пор, можно функционально проанализировать как однопленочную машину Тьюринга («лента», соответствующая их памяти); таким образом, связанная математика может применяться, достаточно абстрагируя их операции. Однако реальные компьютеры имеют ограниченные физические ресурсы, поэтому они являются только линейно ограниченным автоматом . Напротив, универсальный компьютер определяется как устройство с полным набором инструкций по Тьюрингу, бесконечной памятью и бесконечным временем доступности.
В теории вычислимости для описания вычислительной мощности вычислительной системы (например, абстрактной машины или языка программирования ) используются несколько тесно связанных терминов :
Полнота по Тьюрингу
В теории вычислимости исполнитель (множество вычисляющих элементов) называется тьюринг-полным, если на нём можно реализовать любую вычислимую функцию. Другими словами, для каждой вычислимой функции существует вычисляющий её элемент (например, машина Тьюринга) или программа для исполнителя, а все функции, вычисляемые множеством вычислителей, являются вычислимыми функциями (возможно, при некотором кодировании входных и выходных данных).
Название пошло от Алана Тьюринга, который придумал абстрактный вычислитель — машину Тьюринга и дал определение множества функций, вычислимых посредством машин Тьюринга .
Примеры
Большинство широко используемых языков программирования — тьюринг-полные. Это касается как императивных языков, таких как Паскаль, так и функциональных (Haskell) и языков логического программирования (Prolog). Некоторые языки программирования (Haskell, C++) обладают тьюринг-полнотой времени компиляции.
Полными по Тьюрингу являются также неограниченные грамматики.
Библиография
- Brainerd, W.S., Landweber, L.H. Theory of Computation. — Wiley, 1974.
См. также
- Тезис Чёрча
- Машины, которые всегда останавливаются
- Алан Тьюринг
Тьюринг-полнота
Зачастую Тьюринг-эквивалентные языки программирования называют Тьюринг-полными.
В теории вычислимости исполнитель (множество вычисляющих элементов) называется Тьюринг-полным, если на нём можно реализовать любую вычислимую функцию. Другими словами, для каждой вычислимой функции существует вычисляющий её элемент (например, машина Тьюринга) или программа для исполнителя, а все функции, вычисляемые множеством вычислителей, являются вычислимыми функциями (возможно, при некотором кодировании входных и выходных данных).
Любой полный по Тьюрингу язык достаточно универсален, чтобы иметь возможность имитировать любой другой язык (хотя и с потенциальным замедлением в работе). Такие языки эквивалентны в рамках вычислений, которые могут произвести. Полные по Тьюрингу языки настолько распространены, что их можно обнаружить даже в примитивных на первый взгляд системах, например, клеточных автоматах или мозаичных системах.
На практике полнота по Тьюрингу похожа на идеализацию. Компьютеры имеют ограниченное количество памяти, а неограниченная по времени их работа может быть прервана физическим воздействием (выключение, поломка), что как бы ограничивает число задач, которые они могут решить. На самом деле, физические ограничения в контексте Тьюринг-полноты не берутся во внимание: Тьюринг-полный исполнитель не должен быть ограничен по времени и памяти лишь самим исполнителем.
Критерии Тьюринг-полноты
Если на языке программирования можно реализовать машину Тьюринга, то такой язык Тьюринг-полон, и наоборот. Возможность реализации машины Тьюринга на конкретном языке программирования можно грубо описать как перечень требований, которым этот язык должен для этого удовлетворять:
- Конечность (нет бесконечных символьных множеств и пр.).
- Фиксированное описание (формальность [1] ).
- Всегда достаточный объём доступной памяти — в идеале здесь имеется в виду неограниченная память, однако физические рамки не позволяют сделать память ЭВМ бесконечной, поэтому она просто должна быть «always big enough».
- Неограниченность времени выполнения — любая программа в должна иметь возможность работать до тех пор, пока не завершится.
- Возможность функциональной композиции (вызов одной функции из другой, рекурсия).
- Наличие циклов [math][/math] с прерыванием или эквивалентных им конструкций.
- Возможность останавливать выполнение (halt) или каким-то образом подавать сигнал о результатах выполнения.
- Представление множества натуральных чисел, понятие нуля и следующего числа. Возможны другие подобные системы.
- Поддержка входных и выходных данных (I/O), причём без формальных ограничений в объёме. Очевидно, что если любая программа, написанная на каком-то языке программирования, принимает на вход не более фиксированного n бит данных и возвращает не более n бит, этот язык не может быть Тьюринг-полным.
Тьюринг-полнота и неполнота некоторых языков программирования
Доказать Тьюринг-полноту языка программирования можно, предложив способ реализации машины Тьюринга на этом языке. Кроме того, можно предложить на нём интерпретатор Тьюринг-полного языка.
Assembly language
Язык Ассемблера достаточно примитивен относительно языков программирования высокого уровня: он рассчитан на архитектуру с конечной памятью и работает с конечным набором регистров. Однако, не был бы он полным по Тьюрингу, не были бы Тьюринг-полны и любые высокоуровневые языки программирования.
Всё необходимое для машины Тьюринга на asm можно сделать примерно так:
ADDS r0, r0, #1 ; сдвиг ленты вправо ADDS r0, r0, #-1 ; сдвиг ленты влево ADDS [r0], [r0], #1 ; инкремент значения, на которое "указывает" головка ленты ADDS [r0], [r0], #-1 ; декремент значения, на которое "указывает" головка ленты
И далее использовать инструкцию [math]\mathrm[/math] или ей подобную, чтобы выполнять определённую последовательность команд при определённом текущем значении, таким образом обеспечив ветвление.
Pascal
Язык Pascal позволяет смоделировать ленту машины Тьюринга с помощью двунаправленного списка из переменных, создаваемых оператором [math]\mathrm[/math] , семантика которого не предполагает отказа в создании переменной. Также с помощью списков можно смоделировать сколь угодно большие числа. Стандарт не накладывает никаких ограничений: указательный тип абстрактен, множество значений указательного типа языком не ограничено. В Паскале есть еще один тип данных с неограниченным множеством значений, файловый, также пригодный для моделирования ленты машины Тьюринга и представления больших чисел. Достаточно утверждений для очевидности Тьюринг-полноты языка Pascal.
C
В языке C нет высокоуровневого понятия переменной (в смысле Паскаля), есть объекты (object), хранящиеся в памяти как последовательно расположенные байты,имеющие адрес (байты в свою очередь состоят из неадресуемых битов). Целые типы ограничены (конечное множество значений), указатель отождествляется с адресом, постулируется возможность хранить адрес в целочисленной переменной (int или long — зависит от реализации), откуда следует ограниченность множества значений указателей, а стало быть, и ограниченность адресного пространства C-машины. То есть язык C, как и язык ассемблера, ориентирован на архитектуру с конечной памятью. Файл не является типом данных языка C, в отличие от Паскаля. Это вещь из окружения, для работы с которой есть операции над потоками в виде набора библиотечных функций. Тип fpos_t, принятый в стандарте C для позиционирования файлов, постулируется как «отличный от массива тип данных (object type)». Следовательно, множество значений этого типа конечно, а значит, максимальная длина файла в языке C ограничена сверху.
SQL
Сам по себе SQL никогда не считался полным по Тьюрингу языком. Однако, у него существует множество расширений, позволяющих делать рекурсивные запросы, циклы, списки, деревья и пр., например, с помощью PostgreSQL [2] . Более того, на в 2011 г. Habrahabr появилась статья, где показана машина Тьюринга на SQL [3] (в реализации Firebird 2.1, который ограничивает вложенность рекурсивных запросов до 2014 уровней). Тем не менее, всё ещё остаётся ограниченное query execution time.
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++
Шаблоны C++ позволяют производить сложные вычисления ещё на стадии компиляции программы. Впервые это было продемонстрировано Эрвином Унрухом, который реализовал рекурсивный алгоритм распознавания простых чисел в процессе компиляции. Позже в статье Университета Индиана было продемонстрировано кодирование машины Тьюринга в шаблонах C++ [4] .
Java Generics
Аналогично C++ Templates, Generics, несмотря на свои отличия, тоже оказались полными по Тьюрингу, что было подтверждено Раду Григор в одной из статей Кентского Университета [5] .
URISC
URISC (от англ. Ultimate RISC) — предельный случай процессора типа RISC (буквально: компьютер с предельно сокращённым набором инструкций), который умеет выполнять одну-единственную инструкцию. Обычно это «вычесть и пропустить следующую инструкцию, если вычитаемое было больше уменьшаемого» (англ. «reverse-subtract and skip if borrow»). Аналогичная концепция, основанная именно на «вычесть и перейти, если результат не положительный» (англ. «subtract and branch unless positive»), называется SUBLEQ.
URISC также известен в современной литературе как OISC (англ. One Instruction Set Computer) и является полным по Тьюрингу.
mov
Утилита M/o/Vfuscator превращает любую программу на языке C в огромную последовательность из инструкций [math]\mathrm [/math] [6] .