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

Ответ 1

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

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

И тогда, конечно, brainfuck.

Ответ 2

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

Ответ 3

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

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

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

Ответ 4

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

Ответ 5

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

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

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

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

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

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

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

Ответ 6

Язык может или не может делать такие вещи, как: подпрограммы, рекурсия, пользовательские типы данных, циклы, определение классов, goto и т.д. Набор таких языковых функций делает его полным или нет. Например, язык является неполным, если у вас нет циклов, gotos и подпрограмм - вы не можете выполнять циклическую операцию. Языковая полнота - очень теоретическая и научная вещь. Как, например, это доказано, даже если ваш язык не позволяет рекурсивно вызывать функции, но позволяет указывать указатели на функции - вы можете имитировать рекурсию, т.е. С помощью y-combinator.

Вещество, подобное работе с файлами и оборудованием, очень часто не является частью языка. Чтобы выполнить любую задачу программирования, вам нужно больше, чем язык. Вам нужна среда, в которой работает ваша программа. В x86 в качестве языка у вас есть команда "int" с одним параметром, но для выполнения определенных операций при выполнении "int 21h" выполняется OS.

Язык просто нуждается в некотором способе общения с окружающей средой и быть полным - тогда это касается среды для работы с ней. Это допустимо для записи в x86 asm "mov ax, bx", но для выполнения этой операции требуется ваш процессор.

Быть неполным каким-то другим способом - просто, просто определите свою собственную версию полноты. то есть я ненавижу работать без ООП класса, поэтому давайте определим, что язык не является Feldman-complete, если он не имеет языковых функций, поддерживающих ООП на основе классов. Итак, C и Javascript не F-завершены. Вы все еще можете делать что-либо на этих языках и даже имитировать ООП на уровне классов на некоторый уровень.

Что касается ОС - вам все равно нужен процессор, который запускает инструкции и компилятор, который переводит язык в инструкции CPU. Я могу представить, что компилятор переводит что-либо в коды машин. Например, следующий действительный JS-код

for(var i=0;i<10;i++){
 mov("ax",i);
 int(0x21);
}

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

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

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

Ответ 7

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

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

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

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

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

Ответ 8

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

Ответ 9

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

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

• Конечный автомат. Это самый простой класс машин, и они могут распознавать наименьший класс языков, которые, как говорят, являются точными языками, которые могут распознавать регулярные выражения, т.е. начинается ли строка с двух "а" и заканчивается символом "d". Они не могут использоваться для определения того, содержит ли строка сбалансированный набор скобок, fx.
• Нажмите автомат. Это, по сути, расширение Finite Automatons со стеком. В отличие от машин конечного состояния, их можно использовать, чтобы определить, содержит ли конкретная строка сбалансированный набор круглых скобок. Языки, которые нажимают на автоматы, могут распознавать именно тот набор, который может быть описан с использованием контекстно-свободных грамматик, и они часто используются для анализа исходного кода.
• Тьюринговые машины. Здесь самый мощный класс машин, но это не значит, что они могут использоваться для ответа на все вопросы. Они неспособны ответить на вопрос: эта строка описывает машину Тьюринга, которая будет работать навсегда? На самом деле любая машина Тьюринга не может ничего рассказать о нетривиальных свойствах любой машины Тьюринга (теорема Риса).

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

Ответ 10

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

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