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

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

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

programming-languages turing-completeness MaiaVictor
источник

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

Бобсон

@Dokkat Я заново открыл вопрос и удалил обсуждение Meta из комментариев. Обращаем ваше внимание, что если вы не согласны с одним из правил сайта, правильный способ оспорить его - это опубликовать мета-обсуждение; не просто игнорировать это. Кроме того, для субъективных вопросов ключом к успеху является предварительное исследование и строгое определение. Чем больше вы исследуете, тем более конкретным (и ответственным) становится ваш вопрос, и чем дальше вы уходите от пресловутого «неконструктивного» пространства.

Яннис

Кроме того, почему вы считаете "более широкие возможности оптимизации" "большим преимуществом"? Это не означает, что оптимизация не стоит, но я бы не назвал присущую языку оптимизацию «большим преимуществом», учитывая мощь современных компьютеров.

Бобсон

Coq можно считать довольно «мейнстримом» в своей области, причем конкуренты (HOL, Agda, ACL и т. Д.) Гораздо менее заметны.

SK-logic

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

Авив Кон

Ответы:

На сегодняшний день не существует общепринятых многоцелевых языков Тьюринга. Однако существует несколько языков, не соответствующих Тьюрингу. ANSI SQL, регулярные выражения, языки данных (HTML, CSS, JSON и т. Д.) И s-выражения являются некоторыми примечательными примерами.

На самом деле нет пользы для многоцелевых языков, не относящихся к тьюрингу. «Гораздо более анализируемый» аспект, который, как я предполагаю, является намеком на теорему Райса, действительно применим, но он не имеет особого смысла для языков, нацеленных на несколько различных областей применения, другие требования имеют приоритет. Гибкость полноты по Тьюрингу намного важнее, чем ее сложность. Языки программирования, как и любая другая часть программного обеспечения, связаны с компромиссами.

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

Яннис
источник

CSS3 является Тьюринг-полной.

SK-logic

@ SK-logic CSS действительно имеет смысл без HTML, его можно применять к любому виду XML, и ничто не мешает вам реализовать его для любого другого формата с примерно совместимой формой (деревья с именованными узлами, порядок родственных элементов и т. Д.). Я лично написал правила CSS для файла SVG. Это просто гораздо чаще встречается для HTML, потому что HTML гораздо чаще, чем другие форматы.

@ Майк, это неправильная аналогия. Семантика CSS3 тесно связана с семантикой языка представления.

SK-logic

Обратите внимание, что SQL с Windowing и CTE (т. Е. SQL: 2003) также является полным по Тьюрингу.

Йорг Миттаг

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

Йорг Миттаг

-3

Причина того, что неполные языки не являются общепринятыми, заключается в том, что легко реализовать свой собственный язык, когда бы он вам ни понадобился, и, тем не менее, он вам нужен. Интересным примером является биткойн-скрипт: https://github.com/bitcoin/bitcoin/blob/master/src/script.cpp

Адам Куркевич
источник

В самом деле? Имейте в виду реализацию Coq с нуля, самостоятельно, если это так просто?

SK-logic

это только ваше мнение или вы можете как-то это подтвердить?

комнат

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

MauganRa

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

MauganRa