Ответ 1
Во-первых, я полагаю, вы уже слышали о тесте Church-Turing, в котором говорится, что все, что мы называем "вычислением", является тем, что может быть выполнено с помощью машины Тьюринга (или любой из многих других эквивалентных моделей). Таким образом, язык Turing-complete - это тот, в котором могут быть выражены любые вычисления. Наоборот, язык Turing-неполный - это тот, в котором есть некоторые вычисления, которые не могут быть выражены.
Хорошо, это было не очень информативно. Позвольте мне привести пример. Есть одна вещь, которую вы не можете сделать ни на одном языке Turing-неполного: вы не можете написать симулятор машины Тьюринга (иначе вы могли бы кодировать любые вычисления на моделируемой машине Тьюринга).
Хорошо, это все еще не очень информативно. реальный вопрос: какая полезная программа не может быть написана на языке Тьюринга? Ну, никто не придумал определение "полезной программы", которое включает в себя все программы, которые кто-то где-то написал для полезной цели, и это не включает все машинные вычисления Тьюринга. Поэтому разработка Turing-неполного языка, в котором вы можете написать все полезные программы, по-прежнему является очень долгосрочной исследовательской целью.
Теперь существует несколько очень разных типов Turing-неполных языков, и они отличаются тем, чего они не могут сделать. Однако есть общая тема. Если вы разрабатываете язык, существуют два основных способа гарантировать, что язык будет заполнен Тьюрингом:
-
требуют, чтобы язык имел произвольные циклы (
while) и распределение динамической памяти (malloc) -
требуют, чтобы язык поддерживал произвольные рекурсивные функции
Посмотрите на несколько примеров полных языков, отличных от Turing, которые некоторые люди могут, тем не менее, вызывать языки программирования.
-
Ранние версии FORTRAN не имели динамического распределения памяти. Вам нужно было заранее выяснить, сколько памяти потребует ваше вычисление и распределить это. Несмотря на это, FORTRAN когда-то был самым широко используемым языком программирования.
Очевидным практическим ограничением является то, что перед запуском программы необходимо предугадать требования к памяти вашей программы. Это может быть трудным и может быть невозможным, если размер входных данных не ограничен заранее. В то время человек, который кормил входные данные, часто был человеком, который написал программу, поэтому это было не так уж и важно. Но это не так для большинства программ, написанных сегодня.
-
Coq - это язык, разработанный для теорем доказывания. Теперь теоремы доказывания и запущенные программы очень тесно связаны, поэтому вы можете писать программы в Coq так же, как вы доказываете теорему. Интуитивно доказательство теоремы "A означает, что B" является функцией, которая берет доказательство теоремы A как аргумент и возвращает доказательство теоремы B.
Поскольку цель системы - доказать теоремы, вы не можете позволить программисту писать произвольные функции. Представьте, что язык позволил вам написать глупую рекурсивную функцию, которая только что называлась (выберите линию, которая использует ваш любимый язык):
theorem_B boom (theorem_A a) { return boom(a); } let rec boom (a : theorem_A) : theorem_B = boom (a) def boom(a): boom(a) (define (boom a) (boom a))Вы не можете позволить существованию такой функции убедить вас, что A подразумевает B, иначе вы сможете доказать что-либо, а не только истинные теоремы! Таким образом, Coq (и аналогичные теоретические теоремы) запрещают произвольную рекурсию. Когда вы пишете рекурсивную функцию, вы должны доказать, что она всегда заканчивается, так что всякий раз, когда вы запускаете ее на доказательстве теоремы A, вы знаете, что она построит доказательство теоремы B.
Немедленное практическое ограничение Coq заключается в том, что вы не можете писать произвольные рекурсивные функции. Поскольку система должна иметь возможность отклонить все функции, не связанные с завершением, неразрешимость проблемы остановки (или, в более общем смысле, Теорема Риса) гарантирует, что есть также прекращающие функции, которые также отвергаются. Дополнительной практической трудностью является то, что вы должны помочь системе доказать, что ваша функция завершается.
В настоящее время проводится много исследований, направленных на то, чтобы сделать защищенные системы более похожими на язык программирования, не ставя под угрозу их гарантию, что если у вас есть функция от A до B, это не хуже математического доказательства того, что A подразумевает B. Расширение системы принимать больше завершающих функций является одной из тем исследований. Другие направления распространения включают в себя решение таких проблем "реального мира", как ввод/вывод и concurrency. Другая задача состоит в том, чтобы сделать эти системы доступными для простых смертных (или, возможно, убедить простых смертных, что они действительно доступны).
-
Языки синхронного программирования - это языки, предназначенные для программирования систем реального времени, то есть систем, в которых программа должна отвечать меньше, чем n тактов. Они в основном используются для критически важных систем, таких как управление транспортным средством или сигнализация. Эти языки предоставляют надежные гарантии того, сколько времени потребуется программе для выполнения и сколько памяти она может выделить.
Конечно, аналогию таких сильных гарантий является то, что вы не можете писать программы, потребление памяти и время работы которых вы не можете предсказать заранее. В частности, вы не можете записать программу, потребление или время которой зависит от входных данных.
-
Существует много специализированных языков, которые даже не пытаются программировать языки и поэтому могут оставаться вдалеке от полноты Тьюринга: регулярные выражения, языки данных, большинство языков разметки,...
Кстати, Дуглас Хофстадтер написал несколько очень интересных научно-популярных книг об вычислениях, в частности Гёдель, Эшер, Бах: Вечная золотая оплетка. Я не помню, явно ли он обсуждает ограничения Тьюринга-неполноты, но чтение его книг определенно поможет вам понять больше технических материалов.