Практические нетурингово-полные языки?
Почти все используемые языки программирования являются Turing Complete, и хотя это позволяет использовать язык для представления любого вычислимого алгоритма, он также имеет свой собственный набор проблем. Поскольку все написанные мной алгоритмы предназначены для остановки, я хотел бы иметь возможность представлять их на языке, который гарантирует их остановку.
Регулярные выражения, используемые для сопоставления строк и конечных автоматов, используются при лексинге, но мне интересно, есть ли более общий, широко используемый язык, который не является полным по Тьюрингу?
редактировать: я должен уточнить, по "общему назначению" я не обязательно хочу иметь возможность писать все алгоритмы остановки на языке (я не думаю, что такой язык существовал бы), но я подозреваю, что в остановка доказательств, которые могут быть обобщены для создания языка, на котором гарантированно останавливаются все алгоритмы.
Есть и другой способ решения этой проблемы - устранить необходимость в теоретически бесконечной памяти. Как только вы ограничиваете объем памяти, который разрешен машине, число состояний, в которых находится машина, является конечным и счетным, и, следовательно, вы можете определить, остановится ли алгоритм (не позволяя машине перейти в состояние, в котором он находился до этого).).
8 ответов
Не слушай скептиков. Есть очень веские причины, по которым можно предпочесть не полный язык Тьюринга в некоторых контекстах, если вы хотите гарантировать завершение или упростить код, например, удалив возможность ошибок времени выполнения. Иногда просто игнорировать вещи может быть недостаточно.
В статье " Полное функциональное программирование" более или менее убедительно утверждается, что на самом деле мы почти всегда должны предпочитать такой ограниченный язык, потому что гарантии компилятора намного сильнее. Возможность доказать остановку программы может быть значительной сама по себе, но на самом деле это является результатом гораздо более простых рассуждений, которые допускают более простые языки. Являясь одним из компонентов в иерархии языков с различными возможностями, диапазон полезности неуниверсальных языков довольно широк.
Еще одна система, которая более полно обращается к этой многоуровневой концепции, - это Hume. Отчет Юма дает полное описание системы и ее пяти уровней постепенно более полных и все менее безопасных языков.
И, наконец, не забывайте о благотворительности. Это немного абстрактно, но это также очень интересный подход к полезному, но не универсальному языку программирования, который основан непосредственно на понятиях из теории категорий.
BlooP (сокращение от B - округленный цикл) - интересный не полный по Тьюрингу язык. По сути, это язык, полный Тьюринга, с одним (основным) предупреждением: каждый цикл должен содержать ограничение на число итераций. Бесконечные циклы не допускаются. В результате проблема остановки может быть решена для программ BlooP.
Проблема не в машине Тьюринга, а в "алгоритме". Причина, по которой вы не можете предсказать, остановится ли алгоритм или нет, заключается в следующем:
function confusion()
{
if( halts( confusion ) )
{
while True:
no-op
}
else
return;
}
Любой язык, который не может делать рекурсию или циклы, на самом деле не был бы "универсальным".
Регулярные выражения и конечные автоматы - это одно и то же! Лексирование и сопоставление строк - это одно и то же! Причина, по которой FSM останавливаются, заключается в том, что они никогда не зацикливаются они просто передают вход за символом и выходят.
РЕДАКТИРОВАТЬ:
Для многих алгоритмов очевидно, остановятся они или нет.
например:
function nonhalting()
{
while 1:
no-op
}
Эта функция явно никогда не останавливается.
И эта функция, очевидно, останавливается:
function simple_halting_function()
{
return 1;
}
Итак, суть: вы МОЖЕТЕ гарантировать, что ваш алгоритм останавливается, просто спроектируйте его так, чтобы он работал.
Если вы не уверены, остановится ли алгоритм все время; тогда вы, вероятно, не сможете реализовать его на каком-либо языке, который гарантирует "остановку".
Благотворительность не является полной по Тьюрингу, однако она не только теоретически, дидактически интересна (теория категорий), но, кроме того, она может решать практические задачи (Ханойские башни). Его сила настолько велика, что он может выражать даже функцию Аккермана.
Оказывается, довольно легко быть завершенным. Например, вам нужно только 8 инструкций а- ля BrainF ** k, и более того, вам действительно нужна только одна инструкция.
Сердцем этого языка является циклическая конструкция, и как только у вас есть неограниченные циклы, у вас возникает внутренняя проблема остановки. Когда цикл закончится? Даже на языке, не являющемся полным по Тьюрингу, который поддерживает неограниченные циклы, на практике может возникнуть проблема остановки.
Если вы хотите, чтобы все ваши программы заканчивались, вам просто нужно тщательно написать свой код. Конкретный язык может быть больше по вкусу и стилю, но я не думаю, что какой-либо язык может гарантировать абсолютную остановку программы.
"Устранить необходимость теоретически бесконечной памяти". -- Ну, да. Любой физический компьютер ограничен энтропией вселенной и, даже до этого, скоростью света (== максимальная скорость, с которой может распространяться информация).
Еще проще, на физически реализуемом компьютере, просто отслеживать потребление ресурсов и ограничивать его. (т. е. когда потребление памяти или времени> MY_LIMIT, завершить процесс).
Если то, что вы спрашиваете, является чисто математическим / теоретическим решением, как вы определяете "общее назначение"?
ИМХО, правильный способ сделать это состоит в том, чтобы иметь язык, который является полным по Тьюрингу, но обеспечить систему для определения семантики, поддающейся обработке средством проверки корректности.
Затем, предполагая, что вы пишете завершающую программу преднамеренно, вы имеете в виду хороший аргумент о том, почему она останавливается, и с этим новым видом языка вы сможете выразить этот аргумент и доказать его.
Помимо этого, в моем производственном компиляторе у меня есть рекурсии, которые, я знаю, наверняка НЕ остановят определенные входные данные... Я использую неприятный хак, чтобы остановить это: счетчик с "разумным" пределом. К вашему сведению, реальный код задействован в мономорфизированном полиморфном коде, а бесконечное расширение происходит при использовании полиморфной рекурсии. Haskell ловит это, мой компилятор для Феликса - нет (это ошибка в компиляторе, которую я не знаю, как исправить).
Исходя из моего общего аргумента... я бы наверняка хотел узнать, какие аннотации будут полезны для заявленной цели: у меня есть контроль над языком и компилятором, поэтому я мог бы легко добавить такую поддержку, если бы только знал, что именно добавить:) Я видел добавление предложений "инвариант" и "вариант" для циклов для этой цели, хотя я не думаю, что язык расширился для использования этой информации для доказательства завершения (скорее он проверял инвариант и вариант в время выполнения, если я правильно помню).
Может быть, это заслуживает другого вопроса..
Любой не полный по Тьюрингу язык не будет очень полезен в качестве языка общего назначения. Возможно, вам удастся найти что-то, что позиционирует себя как язык общего назначения, не будучи полным по Тьюрингу, но я никогда его не видел.