Практические нетурингово-полные языки?

BlooP (короткий для цикл B ounded ) является интересным неполным по Тьюрингу языком. Это по существу полный по Тьюрингу язык с одним (главным) протестом: каждый цикл должен содержать привязанный количество повторений. Бесконечные циклы не позволяются. В результате Проблема остановки может быть решена для программ BlooP.

Оказывается, что довольно легко быть завершенным Тьюрингом. Например, Вам только нужны эти 8 крыльев инструкций BrainF ** k, и главный, Вам действительно только нужно одна инструкция .

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

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

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

function confusion()
{
    if( halts( confusion ) )
    {
        while True:
            no-op
    }
    else
        return;
}

Любой язык, который не может сделать рекурсии или циклов, действительно не был бы "общего назначения".

Регулярные выражения и конечные автоматы являются тем же самым! Lexing и сопоставление строк являются тем же самым! Причина останов FSMs состоит в том потому что они никогда цикл; они просто передают входной символ символом и выход.

РЕДАКТИРОВАНИЕ:

Для многих алгоритмов, очевидно, остановились ли они.

, например:

function nonhalting()
{
    while 1:
        no-op
}

Эта функция ясно никогда не останавливается.

И, эта функция, очевидно, останавливается:

function simple_halting_function()
{
    return 1;
}

Так нижняя строка: Вы гарантия CAN, что Ваш алгоритм останавливается, просто разработайте его так, чтобы он сделал.

, Если бы Вы не уверены, остановился ли алгоритм все время; тогда Вы, вероятно, не можете реализовать его ни на каком языке, который гарантирует "остановку".

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

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

Еще легче, в физически осуществимом компьютере, просто потребление ресурсов монитора и помещает, некоторые привязали его. (т.е. когда память или потребление времени> MY_LIMIT, уничтожьте процесс).

, Если то, что Вы спрашиваете, является чисто математическим / теоретическое решение, как Вы определяете "общую цель"?

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

В статье Total Functional Programming более или менее убедительно утверждается, что на самом деле мы почти всегда должны предпочесть такой ограниченный язык, потому что гарантии компилятора намного сильнее. Возможность доказать, что программа останавливается, может иметь большое значение сама по себе, но на самом деле это результат гораздо более простых рассуждений, которые позволяют более простые языки. Неуниверсальные языки являются одним из компонентов иерархии языков с разной способностью, поэтому диапазон их применения весьма широк.

Другая система, которая более полно обращается к этой концепции наслоения, - это Hume . Отчет Юма дает полное описание системы и ее пяти уровней все более полных и все менее безопасных языков.

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

Благотворительность не является полной по Тьюрингу, тем не менее, она не только теоретически, дидактически интересна (теория категорий), но, более того, он может решать практические задачи (Ханойские башни). Его сила настолько велика, что может выражать даже функцию Аккермана .