Поскольку существуют не полные по Тьюрингу языки, и, учитывая, что я не изучал Comp Sci в университете, может ли кто-нибудь объяснить что-то, что является неполным по Тьюрингу языком (например, Coq) не может?
Или полнота / неполнота не представляет реального практического интереса (т.е. не имеет большого значения на практике)?
ИЗМЕНИТЬ - я ищу ответ типа вы не можете построить хеш-таблицу на языке, отличном от Тьюринга, из-за X или чего-то в этом роде!
Во-первых, я полагаю, вы уже слышали о тезисе Черча-Тьюринга, в котором говорится, что все, что мы называем «вычислением», можно сделать с помощью машины Тьюринга (или любой из многих других эквивалентных моделей). Таким образом, полный по Тьюрингу язык - это язык, на котором могут быть выражены любые вычисления. И наоборот, неполный по Тьюрингу язык - это язык, в котором есть некоторые вычисления, которые не могут быть выражены.
Хорошо, это было не очень информативно. Приведу пример. Есть одна вещь, которую вы не можете сделать ни на одном языке, неполном по Тьюрингу: вы не можете написать симулятор машины Тьюринга (иначе вы могли бы кодировать любые вычисления на симулированной машине Тьюринга).
Хорошо, это все еще не очень информативно. реальный вопрос в том, какая полезная программа не может быть написана на языке, неполном по Тьюрингу? Что ж, никто не придумал определение «полезная программа», которое включает в себя все программы, которые кто-то где-то написал для полезных целей, и не включает все вычисления на машине Тьюринга. Так что создание неполного по Тьюрингу языка, на котором можно было бы писать все полезные программы, по-прежнему остается очень долгосрочной целью исследования.
Сейчас существует несколько очень разных типов неполных по Тьюрингу языков, и они различаются тем, что не могут делать. Однако есть общая тема. Если вы разрабатываете язык, есть два основных способа гарантировать, что язык будет полным по Тьюрингу:
требовать, чтобы в языке были произвольные циклы (while) и динамическое распределение памяти (malloc)
требовать, чтобы язык поддерживал произвольные рекурсивные функции
Давайте рассмотрим несколько примеров полных по Тьюрингу языков, которые некоторые люди, тем не менее, могут называть языками программирования.
В ранних версиях 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. Расширение системы для принятия большего количества завершающие функции - одна из тем исследования. Другие направления расширения включают решение таких «реальных» проблем, как ввод / вывод и параллелизм. Другая задача - сделать эти системы доступными для простых смертных (или, возможно, убедить простых смертных в том, что они действительно доступны).
Языки синхронного программирования - это языки, разработанные для программирования систем реального времени, то есть систем, в которых программа должна ответ менее чем за n тактов. Они в основном используются для критически важных систем, таких как средства управления транспортными средствами или сигнализация. Эти языки предлагают надежные гарантии того, сколько времени потребуется для запуска программы и сколько памяти она может выделить.
Конечно, аналогом таких сильных гарантий является то, что вы не можете писать программы, потребление памяти и время работы которых вы не можете предсказать заранее. В частности, вы не можете написать программу, потребление памяти или время работы которой зависит от входных данных.
Есть много специализированных языков, которые даже не пытаются быть языками программирования и поэтому могут оставаться комфортно далекими от полноты Тьюринга: регулярные выражения, языки данных, большинство языков разметки, ...
Кстати, Дуглас Хофштадтер написал несколько очень интересных научно-популярных книг о вычислениях, в частности Гёдель, Эшер, Бах: вечная золотая коса. Я не помню, обсуждает ли он явно ограничения неполноты по Тьюрингу, но чтение его книг определенно поможет вам понять больше технического материала.
malloc, вы все равно можете написать свой собственный malloc, используя большие заранее выделенные массивы.
- person Gabe; 27.10.2010
malloc (ну, идеализированный malloc, который позволяет реализовать полный по Тьюрингу язык) с заранее выделенными массивами. Вы все равно позволите своей программе обращаться только к ограниченному количеству памяти; поэтому с теоретической точки зрения все, что у вас есть, - это конечный автомат.
- person Gilles 'SO- stop being evil'; 28.10.2010
malloc заканчивается память. Эта мета-реализация C является полной по Тьюрингу средой программирования.
- person Gilles 'SO- stop being evil'; 28.10.2010
while (...) {n *= 2; realloc(p, n); ...}, чтобы увеличить размер доступной памяти (в конечном итоге вы столкнетесь с ограничением реализации, отсюда и необходимость в мета-реализации). Я думаю (поправьте меня, если я ошибаюсь), что FORTRAN до 95 не имеет подобной функции и, следовательно, более ограничен (я подозреваю, что вы можете писать только примитивные рекурсивные функции или что-то в этом роде).
- person Gilles 'SO- stop being evil'; 28.10.2010
Самый прямой ответ: машина / язык, который не является полным по Тьюрингу, не может использоваться для реализации / моделирования машин Тьюринга. Это происходит из основного определения полноты Тьюринга: машина / язык является завершенным по Тьюрингу, если он может реализовывать / моделировать машины Тьюринга.
Итак, каковы практические последствия? Что ж, есть доказательство того, что все, что можно показать как завершенное по Тьюрингу, может решить все вычислимые проблемы. Что по определению означает, что все, что не является полным по Тьюрингу, имеет недостаток в том, что есть некоторые вычислимые проблемы, которые оно не может решить. Каковы эти проблемы, зависит от того, какие функции отсутствуют, что делает систему несовершенной по Тьюрингу.
Например, если язык не поддерживает циклы или рекурсию или неявно циклы не могут быть завершены по Тьюрингу, потому что машины Тьюринга можно запрограммировать на вечную работу. Следовательно, этот язык не может решать проблемы, требующие циклов.
Другой пример: если язык не поддерживает списки или массивы (или позволяет имитировать их, например, с помощью файловой системы), он не может реализовать машину Тьюринга, потому что машинам Тьюринга требуется произвольный произвольный доступ к памяти. Следовательно, этот язык не может решить проблемы, требующие произвольного произвольного доступа к памяти.
Таким образом, отсутствующая функция, которая классифицирует язык как неполный по Тьюрингу, фактически ограничивает его полезность. Так что ответ зависит от того, что делает язык не-Тьюринговым?
Важный класс проблем, которые плохо подходят для таких языков, как Coq, - это проблемы, окончание которых предположительно или трудно доказать. Вы можете найти множество примеров из теории чисел, возможно, самым известным из них является гипотеза Коллатца
function collatz(n)
while n > 1
if n is odd then
set n = 3n + 1
else
set n = n / 2
endif
endwhile
Это ограничение приводит к тому, что в Coq приходится выражать такие проблемы менее естественным образом.
forall n, exists k, (iterate collatz k) n = 1. (где iterate f k применяет функцию k раз).
- person Olivier Verdier; 07.12.2016
Вы не можете написать функцию, имитирующую машину Тьюринга. Вы можете написать функцию, которая имитирует машину Тьюринга для 2^128 (или 2^2^2^2^128 шагов) и сообщает, приняла ли машина Тьюринга, отклонила или работала дольше разрешенного количества шагов.
Поскольку «на практике» вас уже давно не будет, прежде чем ваш компьютер сможет смоделировать машину Тьюринга для 2^128 шагов, справедливо будет сказать, что неполнота Тьюринга не имеет большого значения «на практике».
