Может ли язык быть полным, но не полным другими способами?
Например, существуют ли определенные вещи при написании операционной системы, которые не могут быть выполнены на языке полного тестирования?
10 ответов
Нет. Или, по крайней мере, если бы вы нашли такой, который опровергает тезис о Тьюринге.
Тем не менее, существуют языки, которые являются законченными по Тьюрингу, но в которых заднице трудно писать определенные программы, например, обработку строк в FORTRAN, числовое программирование в COBOL, целочисленная арифметика в sed, практически все в ассемблере x86.
И тогда, конечно, есть мозговой трах.
Полная по Тьюрингу является наиболее общим формальным определением полноты. Существуют языковые функции, которые необходимы для определенных приложений, но они не вписываются в формальные определения.
Например, графические возможности, способность порождать фоновые процессы, способность сохранять состояние и возможность подключения к сети - все это полезные функции, но они не связаны с полнотой по Тьюрингу. Так что Python на Google App Engine или Java-апплет, работающий в песочнице, все еще завершен по Тьюрингу.
Вы заметите, что во многих случаях эти типы функций предоставляются библиотеками, а не языком ядра.
Да, у вас может быть язык, который не позволяет вам манипулировать оборудованием напрямую. Например, было бы сложно написать операционную систему с использованием оболочки Bourne. Но эти ограничения меньше, чем вы думаете. Операционные системы были написаны на Standard ML, Scheme и даже на Haskell!
Если вы говорите о прагматике, тогда, конечно... вы можете представить себе язык программирования без возможности чтения или записи файлов (например, язык, который может вычислять любую функцию на целых числах, но это все)... Просто потому, что язык может "Управлять моим тостером" не означает, что он не завершен по Тьюрингу, но это означает, что есть вещи, которые он не может сделать, поэтому я не уверен, насколько "важно" или полезно это различие.
В зависимости от контекста "выполнение чего-либо на языке" означает разные вещи для разных людей. Тьюринг - один из тех людей, и он очень точно определил, что он подразумевает под "полным".
Если язык (или теоретическая машина) завершен по Тьюрингу, то нет вычислений по Тьюрингу, которые он не может выполнить. Это не означает, что язык всемогущ, просто он хорош в суммах. Есть много "вещей", которые не являются вычислениями Тьюринга и, следовательно, компьютер, полный Тьюринга, может быть не в состоянии это сделать.
"Будь операционной системой" не является вычислением Тьюринга. Чтобы быть операционной системой, вам нужно делать больше, чем просто вычисления. Вам также нужно манипулировать оборудованием.
Имея полный язык Тьюринга, а также набор операций для выполнения всех необходимых аппаратных манипуляций, включая подходящую концепцию ввода и времени, вы можете написать операционную систему. Или я должен сказать, что можно написать ОС. То, сможете ли вы лично это сделать, зависит от того, насколько легко работать с языком, и от физических ограничений, которые игнорирует определение Тьюринга, таких как то, будет ли результирующая программа действительно помещаться и выполняться в памяти устройства, с которым вы хотите работать, и бежать в реалистичное время.
Несмотря на практические ограничения - да, вы можете написать ОС на любом полном языке Тьюринга, при условии, что в этом языке также достаточно операций для управления оборудованием. "Библиотечные звонки", если вы хотите использовать практический подход CS отличить язык от библиотек. Тьюринг не сделал такого различия, потому что его вычислительная модель в любом случае не имеет понятия "вызова". Вам также необходимо решить проблему начальной загрузки - либо ваше оборудование должно напрямую работать на языке, на котором вы пишете, либо вам нужен компилятор на языке, на котором работает аппаратное обеспечение, либо вам нужен переводчик, написанный на языке, который аппаратное обеспечение работает. Опять же, Тьюринг игнорирует все это, потому что его модель вычислений использует абстрактное оборудование, тогда как написание ОС - это все об оборудовании.
В английском (а не в CompSciSpeak) принято говорить, что в языке "отсутствуют определенные функции", и, возможно, поэтому он "не завершен" по сравнению с другим языком, в котором они есть. Кто-то может возразить, что можно реализовать замыкания в C. Можно, например, написать программу на C, которая является интерпретатором Lisp, и встроить в нее программу Lisp в виде строки. Вуаля, замыкания в Си. Однако, это не то, о чем просит большинство людей, если они скажут: "Я бы хотел, чтобы Си имел замыкания". Если вы думаете, что каждый язык нуждается в замыканиях, то C неполный. Если вы считаете, что каждый язык нуждается в структурированном программировании, то ассемблер ARM неполон. Если вы считаете, что можно динамически добавлять методы к объекту, то C++ неполон, хотя вполне возможно написать класс C++ с помощью методов "AddMethod" и "CallMethodByName" и подделать собственное соглашение о вызовах методов. И так далее.
Тьюринг не думает, что языки нуждаются ни в одном из этих удобств: они не влияют на то, какие вычисления могут быть выполнены, насколько легко писать определенные программы. Концепция полноты по Тьюрингу ничего не говорит о том, как программы выглядят или как они организованы, только о том, что они выводят. Таким образом, эти языки завершены по Тьюрингу, но с точки зрения программиста есть определенные вещи, которые не могут быть выполнены на этих языках.
Язык может или не может делать такие вещи, как: подпрограммы, рекурсия, пользовательские типы данных, циклы, определение классов, переход и т. Д. Набор таких языковых функций делает его полным или нет. Например, язык неполон, если у вас нет циклов, переходов и подпрограмм - вы не можете выполнять какие-либо циклические операции. Полнота языка очень теоретическая и научная вещь. Как, например, это доказано, даже если ваш язык не позволяет рекурсивно вызывать функции, но позволяет указатели на функции - вы можете имитировать рекурсию, то есть с помощью y-комбинатора.
Такие вещи, как работа с файлами и оборудованием, очень часто не являются частью языка. Для выполнения любой задачи программирования вам нужно больше, чем язык. Вам нужна среда, в которой работает ваша программа. В x86 в качестве языка у вас есть инструкция "int" с одним параметром, но это зависит от ОС, которая выполняет определенные операции при выполнении "int 21h".
Язык просто нуждается в некотором способе общения с окружающей средой и быть полным - тогда это зависит от среды, чтобы работать с ним. Допустимо написать в x86 asm "mov ax,bx", но это зависит от вашего процессора, чтобы выполнить эту операцию.
Быть неполным каким-то другим способом - легко, просто определите свою собственную версию полноты. т.е. я ненавижу работать без ООП на основе классов, поэтому давайте определим, что язык не является полным по Фельдману, если у него нет языковых функций, поддерживающих ООП на основе классов. Хорошо, тогда C и Javascript не F-полны. Вы все еще можете делать что-либо на этих языках и даже имитировать ООП на уровне классов до некоторого уровня.
Что касается ОС - вам все еще нужен процессор, который выполняет инструкции, и компилятор, который переводит язык в инструкции процессора. Я могу представить, что компилятор переводит что-либо в машинные коды Например, следующий действительный код JS
for(var i=0;i<10;i++){
mov("ax",i);
int(0x21);
}
и не должно быть так сложно скомпилировать его в машинный код.
В современном мире вы выбираете не только язык, вы также выбираете платформу, стандартные и нестандартные библиотеки, литературу, сообщество, поддержку и т. Д. Все эти вещи влияют на вашу способность делать определенные вещи, и все они могут быть или не быть "достаточно" для вашей задачи. Но если я не могу скомпилировать код с ++ в java-апплет, это не значит, что это неполность языка с ++. Это просто отсутствие компилятора, который преобразует код C++ во что-то, что может быть загружено JVM.
Если вы хотите, вы можете разработать язык с такими языковыми функциями, как "OpenFile, PingNetworkHost, DownloadMpeg4FileOverHttpsAndPlayBackwards". Но если в языке их нет, они все равно могут быть реализованы с использованием других языковых функций и поддержки среды, поэтому отсутствие таких функций не делает язык неполным. Если ваш язык похож на C, но без оператора goto, оператора цикла (for,while,do while) и функций, то вы не можете писать циклические программы, и никакие окружение и библиотеки не могут вам помочь.
Ответ является наиболее определенным, да. Полнота по Тьюрингу только подразумевает, что полный язык Тьюринга может использоваться для вычисления любой вычислимой функции. С одной стороны, это ничего не говорит о сложности вычислений.
Обычно можно ожидать, что любой алгоритм за полиномиальное время может быть выражен как алгоритм за полиномиальное время на любом другом полном языке Тьюринга, но это все. Особенно любые требования в реальном времени (мягкие или жесткие) выходят за пределы окна, если вы концентрируетесь только на полноте по Тьюрингу.
Другая важная вещь - это выразительность языка, которая в значительной степени является субъективным свойством, но вы можете понять, что программы гораздо сложнее писать в любом машинном коде, чем, скажем, Java.
Что касается операционных систем, интерфейс с аппаратным обеспечением является обязательным, но любой язык может быть снабжен такими утилитами.
[Править] Еще одна вещь, которую я мог бы добавить, - это то, что никакая реальная реализация любого языка программирования не является полной по Тьюрингу по природе наших конечных вычислительных машин. Хотя тезис Черча-Тьюринга и связанные с ним оригинальные открытия (например, проблема остановки) закладывают фундамент нашего понимания вычислительной техники, они редко встречаются в мире практических вычислений.
Когда речь идет о языках, обычно предполагается, что языки работают на некоторых очень простых машинах. Таким образом, любая концепция чтения из файла или доступа к сети обычно не рассматривается в отношении мощности языка.
Существуют разные классы языков, которые часто используются в теории вычислимости (каждый с почти бесконечными модификациями)
- Конечный автомат. Это самый простой класс машин, и они могут распознавать наименьший класс языков, который является точным языком, который могут распознавать регулярные выражения, т.е. начинается ли строка с двух 'a' и заканчивается d. Их нельзя использовать для распознавания, содержит ли строка сбалансированный набор скобок, fx.
- Нажмите вниз автомат. По сути, это расширение конечных автоматов со стеком. В отличие от конечных автоматов, они могут использоваться для определения того, содержит ли конкретная строка сбалансированный набор скобок. Языки, которые могут распознать автоматы, являются именно тем набором, который можно описать с помощью контекстно-свободных грамматик, и они часто используются для анализа исходного кода.
- Машины Тьюринга. Это самые мощные машины этого класса, но это не значит, что их можно использовать для ответов на все вопросы. Они не могут ответить на вопрос, описывает ли эта строка машину Тьюринга, которая будет работать вечно? Фактически, любая машина Тьюринга не может ничего рассказать о нетривиальных свойствах любой машины Тьюринга (теорема Райса).
Так что да, у машины Тьюринга есть ограничения, и есть классы машин, которые могут делать то, что машина Тьюринга не может, но они есть (все будут, по всей вероятности) только когда-либо существовавшими в теории, более новыми на практике.
Я не думаю, что определения полноты, отличные от Тьюринга (или регулярные выражения, или автоматные выпадающие), актуальны для языков. Но эта полнота только в отношении числовых или символических вычислительных средств.
То, что вы упоминаете, мне кажется, больше зависит от времени выполнения и среды, чем от языка. Здесь есть важное различие, и формальные понятия полноты обычно относятся только к самим языкам.