Языком может быть Тьюринг, завершенный но неполный другими способами?

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

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

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

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

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

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

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

Yes, you can have a language that does not allow you to manipulate the hardware directly. It would be hard to write an operating system using the Bourne shell, for example. But these limitations are less than you think. Operating systems have been written in Standard ML, Scheme, and even Haskell!

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

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

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

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

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

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

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

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

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

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

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

Итак, да, машина Тьюринга имеет ограничения,