Может ли язык быть полноценным, но не полным другими способами?

Question

Например, существуют ли определенные вещи при написании операционной системы, которые не могут быть выполнены на языке полного тестирования?

Answer 1

Нет. или, по крайней мере, если бы вы нашли тот, который был бы опровергнутым тезисом Тьюринга Церкви .

Тем не менее, существуют языки, которые являются законченными по Тьюрингу, но в которых заднице сложно писать определенные программы, например, обработку строк в FORTRAN, числовое программирование в COBOL, целочисленная арифметика в sed, практически все в ассемблере x86 .

И, конечно же, есть блядь .

Answer 2

Тьюринг-полнота является наиболее общим формальным определением полноты. Существуют языковые функции, которые необходимы для определенных приложений, но они не вписываются в формальные определения.

Например, графические возможности, способность порождать фоновые процессы, способность сохранять состояние и возможность подключения к сети - все это полезные функции, но они не связаны с полнотой по Тьюрингу. Таким образом, Python в Google App Engine или Java-апплет, работающий в песочнице, все еще завершен по Тьюрингу.

Вы заметите, что во многих случаях эти типы функций предоставляются библиотеками, а не языком ядра.

Answer 3

Да, у вас может быть язык, который не позволяет вам манипулировать оборудованием напрямую. Например, было бы сложно написать операционную систему с использованием оболочки Bourne. Но эти ограничения меньше, чем вы думаете. Операционные системы были написаны на Standard ML, Scheme и даже Haskell !

Answer 4

Если вы говорите о прагматике, тогда, конечно ... вы можете представить себе язык программирования без возможности чтения или записи файлов (например, язык, который может вычислять любую функцию на целых числах, но это все) ... Тот факт, что мой тостер не может работать с языком, не означает, что он не завершен по Тьюрингу, но означает, что есть вещи, которые он не может сделать , поэтому я не уверен, насколько «важно» или полезно это различие.

Answer 5

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

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

«Будь операционной системой» не является вычислением Тьюринга. Чтобы быть операционной системой, вам нужно делать больше, чем просто вычисления. Вам также нужно манипулировать оборудованием.

Учитывая полный язык Тьюринга, а также набор операций для выполнения всех необходимых аппаратных манипуляций, включая подходящую концепцию ввода и времени, вы можете написать операционную систему. Или я должен сказать, что можно написать ОС. То, сможете ли вы лично это сделать, зависит от того, насколько легко работать с языком, и от физических ограничений, которые игнорирует определение Тьюринга, таких как то, будет ли результирующая программа фактически помещаться и выполняться в памяти устройства, с которым вы хотите работать, и беги в реалистичное время.

Несмотря на практические ограничения - да, вы можете написать ОС на любом полном языке Тьюринга, при условии, что в этом языке также достаточно операций для управления оборудованием. «Библиотечные звонки», если вы хотите использовать практический подход CS отличить язык от библиотек. Тьюринг не сделал такого различия, потому что его вычислительная модель в любом случае не имеет понятия «вызова». Вам также необходимо решить проблему с загрузкой - либо ваше оборудование должно напрямую работать на языке, на котором вы пишете, либо вам нужен компилятор на язык, на котором работает оборудование, или вам нужен переводчик, написанный на языке, который аппаратное обеспечение работает. Опять же, Тьюринг игнорирует все это, потому что его вычислительная модель использует абстрактное оборудование, тогда как написание ОС - это все об оборудовании.

В английском (а не в CompSciSpeak) принято говорить, что в языке «отсутствуют определенные функции» и, возможно, поэтому он «не завершен» по сравнению с другим языком, в котором они есть. Кто-то может возразить, что можно реализовать замыкания в C. Можно, например, написать программу на C, которая является интерпретатором Lisp, и встроить в нее программу Lisp в виде строки. Вуаля, замыкания в Си. Однако, это не то, о чем просит большинство людей, если они скажут: «Я бы хотел, чтобы Си имел замыкания». Если вы думаете, что каждый язык нуждается в замыканиях, то C неполный. Если вы думаете, что каждый язык нуждается в структурированном программировании, то ассемблер ARM неполон. Если вы считаете, что можно динамически добавлять методы к объекту, то C ++ неполон, хотя вполне возможно написать класс C ++ с помощью методов «AddMethod» и «CallMethodByName» и подделать собственное соглашение о вызовах методов. И так далее.

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

Answer 6

Язык может или не может делать такие вещи, как - подпрограммы, рекурсия, пользовательские типы данных, циклы, определение классов, переход и т. Д. Набор таких языковых функций делает его полным или нет. Например, язык неполон, если у вас нет циклов, переходов и подпрограмм - вы не можете выполнять какие-либо циклические операции. Полнота языка очень теоретическая и научная вещь. Как, например, это доказано, чем, даже если ваш язык не позволяет рекурсивно вызывать функции, но допускает указатели на функции - вы можете имитировать рекурсию, то есть с помощью 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);
}

и не должно быть так сложно скомпилировать его в машинный код.

В современном мире вы выбираете не только язык, вы также выбираете платформу, стандартные и нестандартные библиотеки, литературу, сообщество, поддержку и т. Д. Все эти вещи влияют на вашу способность делать определенные вещи, и в целом они могут быть или может быть "недостаточно полным" для вашей задачи. Но если я не могу скомпилировать код c ++ в java-апплет, это не значит, что это неполность языка c ++. Это просто отсутствие компилятора, который преобразует код c ++ во что-то, что может быть загружено JVM.

Если вы хотите, вы можете создать язык с такими языковыми функциями, как «OpenFile, PingNetworkHost, DownloadMpeg4FileOverHttpsAndPlayBackwards». Но если в языке их нет, они все равно могут быть реализованы с помощью других языковых функций и поддержки среды, поэтому отсутствие таких функций не делает язык неполным. Если ваш язык похож на C, но без оператора goto, оператора цикла (for, while, do while) и функций, то вы не можете писать циклические программы, и никакие окружение и библиотеки вам не помогут.

Answer 7

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

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

Еще одна важная вещь - выразительность языка, которая в значительной степени является субъективным свойством, но вы можете понять, что программы гораздо сложнее писать в любом машинном коде, чем, скажем, Java.

Что касается операционных систем, интерфейс с аппаратным обеспечением является обязательным, но такие утилиты могут быть установлены на любом языке.

[Изменить] Еще одна вещь, которую я могу добавить, это то, что ни одна реальная реализация какого-либо языка программирования не является полной по Тьюрингу по природе наших конечных вычислительных машин. Несмотря на то, что тезис Черча-Тьюринга, а также связанные с ним оригинальные открытия (например, проблема остановки) закладывают основу для нашего понимания вычислительной техники, они редко встречаются в мире практических вычислений.

Answer 8

Я не думаю, что определения полноты, отличные от Тьюринга (или регулярные выражения, или автоматные выпадающие), актуальны для языков . Но эта полнота касается только числовых или символических вычислительных средств.

Вещи, о которых вы говорите, кажутся мне скорее функцией времени выполнения и среды, чем языком. Здесь есть важное различие, и формальные понятия полноты обычно относятся только к самим языкам.

Answer 9

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

Существуют разные классы языков, которые часто используются в теории вычислимости (каждый с почти бесконечными модификациями)

1. Конечный автомат. Это самый простой класс машин, и они могут распознавать наименьший класс языков, который является точным языками, которые могут распознавать регулярные выражения, т.е. начинается ли строка с двух 'a' и заканчивается d. Их нельзя использовать для распознавания, содержит ли строка сбалансированный набор скобок, fx.
2. Нажмите на автомат. По сути, это расширение конечных автоматов со стеком. В отличие от конечных автоматов, они могут использоваться для определения, содержит ли конкретная строка сбалансированный набор скобок. Языки, которые могут распознать автоматы, могут точно набор, который можно описать с помощью контекстно-свободных грамматик, и они часто используются для анализа исходного кода.
3. Машины Тьюринга. Это самые мощные машины этого класса, но это не значит, что их можно использовать для ответов на все вопросы. Они не могут ответить на вопрос, описывает ли эта строка машину Тьюринга, которая будет работать вечно? Фактически, любая машина Тьюринга не может ничего рассказать о нетривиальных свойствах любой машины Тьюринга (теорема Райса).

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

Answer 10

Неполное удобство использования:)