Может ли язык быть полным по Тьюрингу, но неполным в других отношениях?
https://stackoverflow.com/questions/813657
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Например, существуют ли определенные вещи при написании операционной системы, которые не могут быть выполнены на языке, полном по Тьюрингу?
Решение
Нет.или, по крайней мере, если бы вы нашли что-то такое, что опровергло бы Тезис Черча Тьюринга.
Однако существуют языки, которые являются полными по Тьюрингу, но на которых писать определенные программы - сплошная мука в заднице, т.Е. обработка строк на FORTRAN, числовое программирование на COBOL, целочисленная арифметика на sed, практически все на ассемблере x86.
И тогда, конечно, есть мозгобойня.
Другие советы
Да, у вас может быть язык, который не позволяет вам манипулировать оборудованием напрямую. Например, было бы сложно написать операционную систему с использованием оболочки Bourne. Но эти ограничения меньше, чем вы думаете. Операционные системы были написаны на стандартном ML, Scheme и даже на Haskell !
Тьюрингово-полное является наиболее общим формальным определением полноты. Существуют языковые функции, которые необходимы для определенных приложений, но они не вписываются в формальные определения.
Например, графические возможности, способность порождать фоновые процессы, способность сохранять состояние и возможность подключения к сети - все это полезные функции, но они не связаны с полнотой по Тьюрингу. Таким образом, Python в Google App Engine или Java-апплет, работающий в песочнице, все еще завершен по Тьюрингу.
Вы заметите, что во многих случаях эти типы функций предоставляются библиотеками, а не языком ядра.
Если вы говорите о прагматике, тогда, конечно ... вы можете представить себе язык программирования без возможности чтения или записи файлов (например, язык, который может вычислять любую функцию на целых числах, но это все) ... То, что язык не может работать с моим тостером, не означает, что он не завершен по Тьюрингу, но это означает, что есть вещи, которые он не может делать , поэтому я не уверен, насколько «важно» или полезно это различие .
В зависимости от контекста "выполнение чего-либо на языке" означает разные вещи для разных людей. Тьюринг - один из тех людей, и он очень точно определил, что он подразумевает под «полным».
Если язык (или теоретическая машина) завершен по Тьюрингу, то не существует вычислений Тьюринга, которые он не может выполнить. Это не означает, что язык всемогущ, просто он хорош в суммах. Есть много «вещей» которые не являются вычислениями Тьюринга и, следовательно, компьютер, полный Тьюринга, может быть не в состоянии.
" быть операционной системой " это не вычисление Тьюринга. Чтобы быть операционной системой, вам нужно делать больше, чем просто вычисления. Вам также нужно манипулировать оборудованием.
Учитывая полный язык Тьюринга, а также набор операций для выполнения всех необходимых аппаратных манипуляций, включая подходящую концепцию ввода и времени, вы можете написать операционную систему. Или я должен сказать, что можно написать ОС. То, сможете ли вы лично это сделать, зависит от того, насколько легко работать с языком, и от физических ограничений, которые игнорирует определение Тьюринга, таких как то, будет ли результирующая программа фактически помещаться и выполняться в памяти устройства, с которым вы хотите работать, и бежать в реалистичное время.
Несмотря на практические ограничения - да, вы можете написать ОС на любом полном языке Тьюринга, при условии, что в этом языке также достаточно операций для управления оборудованием. " Библиотечные вызовы " ;, если вы хотите использовать практический подход CS, позволяющий отличать язык от библиотек. Тьюринг не сделал такого различия, потому что его вычислительная модель не имеет понятия «вызова». тем не мение. Вам также необходимо решить проблему с загрузкой - либо ваше оборудование должно напрямую работать на языке, на котором вы пишете, либо вам нужен компилятор на язык, на котором работает оборудование, или вам нужен переводчик, написанный на языке, который аппаратное обеспечение работает. Опять же, Тьюринг игнорирует все это, потому что его модель вычислений использует абстрактное оборудование, тогда как написание ОС - это все об оборудовании.
В английском (а не в CompSciSpeak) принято говорить, что в языке "отсутствуют определенные функции" и, возможно, поэтому он "не завершен". по сравнению с другим языком, который имеет их. Кто-то может возразить, что можно реализовать замыкания в C. Можно, например, написать программу на C, которая является интерпретатором Lisp, и встроить в нее программу Lisp в виде строки. Вуаля, замыкания в С. Однако большинство людей спрашивают не об этом, если они скажут: «Хотелось бы, чтобы у С были замыкания». Если вы думаете, что каждый язык нуждается в замыканиях, то C неполный. Если вы думаете, что каждый язык нуждается в структурированном программировании, то ассемблер ARM неполон. Если вы считаете, что можно динамически добавлять методы к объекту, то C ++ неполон, хотя вполне возможно написать класс C ++ с помощью " AddMethod " и " CallMethodByName " методы и подделать ваше собственное соглашение о вызове методов оттуда. И так далее.
Тьюринг не думает, что языки нуждаются ни в одном из этих удобств: они не влияют на то, какие вычисления могут быть выполнены, просто на то, насколько легко писать определенные программы. Концепция полноты по Тьюрингу ничего не говорит о том, как программы выглядят или как они организованы, только из того, что они выводят. Таким образом, эти языки завершены по Тьюрингу, но с точки зрения программиста есть определенные вещи, которые не могут быть выполнены на этих языках.
Язык может или не может выполнять такие функции, как: подпрограммы, рекурсия, пользовательские типы данных, циклы, определение классов, переход и т. д. Набор таких языковых функций делает его полным или нет. Например, язык неполон, если у вас нет циклов, переходов и подпрограмм - вы не можете выполнять какие-либо циклические операции. Полнота языка очень теоретическая и научная вещь. Как, например, доказано, чем, даже если ваш язык не позволяет рекурсивно вызывать функции, но допускает указатели на функции - вы можете имитировать рекурсию, то есть с помощью y-combinator.
Такие вещи, как работа с файлами и оборудованием, очень часто не являются частью языка. Для выполнения любой задачи программирования вам нужно больше, чем язык. Вам нужна среда, в которой работает ваша программа. В 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) и функций, то вы не можете писать циклические программы, и никакие окружение и библиотеки не могут вам помочь.
Ответ - самое определенное "да".Полнота по Тьюрингу подразумевает только то, что полный язык по Тьюрингу может быть использован для вычисления любой вычислимой функции.Во-первых, это ничего не говорит о сложности вычислений.
Обычно вы можете ожидать, что любой алгоритм за полиномиальное время может быть выражен как алгоритм за полиномиальное время на любом другом полном языке Тьюринга, но не более того.Особенно любые требования к реальному времени (мягкие или жесткие) выходят за рамки, если вы сосредоточены только на полноте по Тьюрингу.
Другой важной вещью является выразительность языка, которая в значительной степени является субъективным свойством, но вы можете оценить, что программы гораздо сложнее писать в любом машинном коде, чем, скажем, на Java.
Что касается операционных систем, то интерфейс к аппаратному обеспечению является обязательным, но такие утилиты могут быть установлены на любом языке.
[Редактировать] Еще одна вещь, которую я мог бы добавить, это то, что ни одна фактическая реализация какого-либо языка программирования не является полной по Тьюрингу в силу природы наших конечных вычислительных машин.Хотя тезис Черча-Тьюринга, наряду с связанными с ним основополагающими открытиями (такими как проблема остановки), закладывает основу для нашего понимания вычислительной техники, они редко встречаются в мире практических вычислений.
Неполное удобство использования:)
Когда речь идет о языках, обычно предполагается, что языки работают на некоторых очень простых машинах. Таким образом, любая концепция чтения из файла или доступа к сети обычно не рассматривается в отношении мощности языка.
Существуют разные классы языков, которые часто используются в теории вычислимости (каждый с почти бесконечными модификациями)
<Ол>Так что да, у машины Тьюринга есть ограничения, и есть классы машин, которые могут делать то, что машина Тьюринга не может, но у них (все будет, по всей вероятности) только когда-либо существовавшие в теории, более новые на практике.
Я не думаю, что определения полноты, кроме тьюринга (или регулярные выражения, или автоматные выпадающие), актуальны для языков . Но эта полнота относится только к числовым или символическим вычислительным средствам.
Вещи, о которых вы говорите, кажутся мне скорее функцией времени выполнения и среды, чем языком. Есть важное различие, и формальные понятия полноты обычно относятся только к самим языкам.
