Критерии, чтобы определить, является ли это язык программирования
Какие критерии или основные функции необходимы, чтобы сказать, что X или Y является (или не является) языком программирования?
Я немного прочел ( HTML считается языком программирования?, завершен по Тьюрингу и т. Д.) И пришел к выводу, что язык или синтаксис должен быть полным по Тьюрингу, чтобы считаться языком программирования. Это правильно? Это достаточно?
И как мне определить, завершен ли Тьюринг? Есть ли конкретные критерии?
Достаточно ли иметь структуры управления потоком (условные операторы и циклы), чтобы считать Тьюринг завершенным?
4 ответа
Существуют языки программирования, которые не являются полными по Тьюрингу. Некоторые примеры языков, не являющихся полными по Тьюрингу, смотрите на: Практические языки, не полные по Тьюрингу?
Преимущество наличия языка, который не является полным по Тьюрингу, может заключаться, например, в том, что этого может быть достаточно для выполнения необходимых задач, при этом достаточно просто, чтобы позволить вам доказать свойства своих программ, которые вы не могли бы доказать иначе. Это может быть полезно, например, в случаях, когда важно знать, что программа будет работать без ошибок.
Что именно составляет язык программирования, немного расплывчато, но можно сказать, что это язык, на котором вы можете выражать вычисления. Если мы посмотрим на HTML, вы не сможете создать документ, который вычисляет что-либо; это просто говорит браузеру, как должна выглядеть страница. Важно отметить, что ничего нового не вычисляется.
Это, как говорит Марсело, довольно размыто.
Что касается определения того, является ли язык полным по Тьюрингу, я отсылаю вас к этому вопросу: каковы практические рекомендации по оценке " полноты по Тьюрингу" языка?
Какие критерии или основные функции необходимы, чтобы сказать, что X или Y является (или не является) языком программирования?
Как уже сказал Марсело Кантос, это несколько нечетко, тем более что существуют специфичные для домена языки (DSL; http://en.wikipedia.org/wiki/Domain-specific_language), которые не являются полными по Тьюрингу, но также часто рассматриваются как языки программирования.
И как мне определить, завершен ли Тьюринг? Есть ли конкретные критерии?
Один из способов определить, является ли язык программирования полным по Тьюрингу, - написать на нем машину Тьюринга (или реализацию лямбда-исчисления).
Другой способ - доказать, что все мюрекурсивные функции http://en.wikipedia.org/wiki/%CE%9C-recursive_function могут быть вычислены языком программирования.
Поскольку можно доказать, что императивный язык программирования является полным по Тьюрингу, если есть присвоение переменной, способ представления числа 0, функция-преемник, функция-предшественник и возможность представления циклов while, это еще один способ.
Иногда используемый способ (который по очевидным причинам не всегда работает) доказать, что язык программирования не является полным по Тьюрингу, состоит в проверке завершения всех программ; если да, этого не может быть
Итак, давайте подумаем о последствиях этих конкретных определений:
Полный по Тьюрингу язык - это язык программирования: CSS становится языком программирования.
Язык программирования должен быть полным по Тьюрингу: возможно, но программы могут быть написаны иначе.
Теперь гораздо лучшее определение: язык программирования - это язык, который можно использовать для написания программ.
Термин "язык программирования" несколько нечеткий. Регулярные выражения составляют язык программирования? Большинство программистов сказали бы "да", хотя регулярные выражения еще не завершены.
Что касается полноты по Тьюрингу, я не эксперт, но я думаю, что достаточно иметь условную ветвь и бесконечный стек (поэтому на реальной машине только приблизительная полнота по Тьюрингу).
РЕДАКТИРОВАТЬ: После небольшого исследования, я обнаружил, что этого недостаточно. Вам нужно как минимум два стека и минимальное количество состояний (и таблица переходов состояний).
Возможно, более практичным критерием является то, что если вы можете запомнить произвольное количество состояний и выполнить циклы, это, вероятно, завершается.