Критерии, чтобы определить, является ли это язык программирования

Question

Какие критерии или основные функции необходимы, чтобы сказать, что X или Y является (или не является ) программированием язык

Я немного прочел ( Считается ли HTML языком программирования? , Тьюринг завершен и другие ) и пришел к выводу, что язык или синтаксис должен быть завершен по Тьюрингу , чтобы считаться языком программирования. Это правильно? Этого достаточно?

А как определить, что-то Тьюринг завершено ? Есть ли какие-то конкретные критерии?

Достаточно ли иметь структуры управления потоком (условные операторы и циклы), чтобы считаться Тьюринг завершен ?

Answer 1

Существуют языки программирования, которые не являются полными по Тьюрингу.Для некоторых примеров языков, не являющихся полными по Тьюрингу, взгляните на: Практические языки, не полные по Тьюрингу?

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

То, что именно представляет собой язык программирования, немного расплывчато, но можно сказать, что это язык, на которомВы можете выразить вычисления.Если мы посмотрим на HTML, вы не сможете создать документ, который вычисляет что-либо;это просто говорит браузеру, как должна выглядеть страница.Важно отметить, что он не вычисляет ничего нового.

Это, как говорит Марсело, довольно нечетко.

Что касается определения того, является ли язык полным по Тьюрингу, я отошлю вас к этому вопросу: Каковы практические рекомендации по оценке "полноты по Тьюрингу" языка?

Answer 2

Какие критерии или основные функции необходимы для того, чтобы сказать, что X или Y является (или не является) языком программирования?

Как уже сказал Марсело Кантос, это несколько нечетко,тем более, что существуют специфичные для домена языки (DSL; http://en.wikipedia.org/wiki/Domain-specific_language), которые не являются полными по Тьюрингу, но также часто считаются языками программирования.

И как определить, завершено ли что-то по Тьюрингу?Есть какие-то конкретные критерии?

Один из способов определить, является ли язык программирования завершенным по Тьюрингу, - написать на нем машину Тьюринга (или реализацию лямбда-исчисления).

Другой способчтобы доказать, что все мюрекурсивные функции http://en.wikipedia.org/wiki/%CE%9C-recursive_function могут быть вычислены с помощью языка программирования.

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

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

Answer 3

Итак, давайте подумаем о последствиях этих конкретных определений:

Turing-complete язык - это язык программирования: CSS становится языком программирования .

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

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

Answer 4

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

Что касается полноты по Тьюрингу, я не эксперт, но я думаю, что достаточно иметь условную ветвь и бесконечный стек (поэтому на реальной машине только приблизительная полнота по Тьюрингу).

РЕДАКТИРОВАТЬ: После небольшого исследования, я обнаружил, что этого недостаточно. Вам нужно как минимум два стека и минимальное количество состояний (и таблица переходов между состояниями).

Возможно, более практичным критерием является то, что, если вы можете помнить произвольное количество состояний и делать циклы, это, вероятно, завершается.