Да и нет.Не существует известной модели вычислений, которая могла бы делать то, что могут делать машины Тьюринга, и все еще называться вычислением, в отличие от магии¹.Следовательно, в этом смысле нет ничего, кроме полноты Тьюринга.
С другой стороны, вы можете быть знакомы с высказыванием, что «нет проблемы, которая не может быть решена путем добавления слоя косвенности».Таким образом, мы могли бы хотеть различать модели вычислений, которые отображаются непосредственно на машины Тьюринга, и модели вычислений, которые требуют уровня косвенности.«Добавление уровня косвенности» не является точным математическим понятием в целом, но во многих конкретных случаях вы можете наблюдать уровень косвенности.Часто самый простой способ доказать, что некоторая парадигма вычислений вычислима по Тьюрингу, - написать для него интерпретатор на машине Тьюринга, и это точно уровень косвенности.
Итак, давайте посмотрим, что это такое.означает моделирование параллелизма.Вы упомянули способность «выполнять вещи, чтобы они происходили точно одновременно».Это особый тип параллелизма, называемый параллелизм , и, насколько это возможно, это модель с очень ограниченными возможностями.Мир параллелизма намного более дикий, чем этот.Тем не менее, параллелизм уже допускает вещи, которые требуют некоторой формы косвенного обращения при моделировании на машине Тьюринга.
Рассмотрим следующую проблему: при наличии компьютерных программ A и B (переданных на ленте универсальной машины Тьюринга) их выполнитьоба, и вернуть результат любой программы;Ваша программа должна завершиться, если только A и B не являются завершающими.В чисто последовательном мире вы можете выполнить A и вернуть результат;или вы можете выполнить B и вернуть результат.Но если вы начнете с выполнения A, а программа B не завершится, а B завершится, то ваша стратегия выполнения не решит проблему.И точно так же, если вы начнете с выполнения B, ваша стратегия выполнения не решит проблему, потому что B может не завершиться, даже если A делает.из которых выполнить первым на этом.Однако существует очень простой способ изменить машину Тьюринга для параллельного выполнения программ: поместите A и B на отдельные ленты, продублируйте ваш автомат и выполняйте один шаг каждой программы, пока одна из двух не завершится.Добавив этот уровень обработки, вы можете решить проблему параллельного выполнения.
Решение этой проблемы потребовало лишь небольшой модификации модели (легко моделировать машину Тьюринга с двумя лентами с машиной с одной лентой)).Тем не менее, я упоминаю об этом, потому что это важный пример в [лямбда-исчислении] (http://en.wikipedia.org/wiki/Lambda исчисление), еще одной важной модели вычислений.Операция сокращения (оценки) двух лямбда-членов параллельно, пока один из них не достигнет нормальной формы (завершается), называется параллелью Плоткина или .Известно, что невозможно написать лямбда-термин (программу лямбда-исчисления), который реализует параллельный или.Следовательно, лямбда-исчисление называется «по существу последовательным».
Причина, по которой я упоминаю здесь лямбда-исчисление, состоит в том, что большинство языков программирования ближе к лямбда-исчислению, чем к машине программирования.Поэтому, как программист, понимание лямбда-исчисления часто более важно, чем понимание машин Тьюринга.Пример параллельного или показывает, что добавление параллелизма к языку² может открыть возможности, которые недоступны в исходном языке.
Можно добавить параллелизм к последовательному языку, по сути, с помощью того же трюка, что и на машинах Тьюринга:выполнить маленький кусочек нити A, затем маленький кусочек нити B и так далее.Фактически, если вы этого не сделаете на своем языке, ядро операционной системы обычно может сделать это за вас.Строго говоря, это обеспечивает одновременное выполнение потоков, но при этом все равно используется один процессор.
В качестве теорииЭта модель многопоточного исполнения страдает от ограничения, детерминированного .Действительно, любая система, которая может быть смоделирована непосредственно на машинах Тьюринга, является детерминированной.При работе с параллельными системами часто важно иметь возможность писать недетерминированные программы.Часто точный порядок, в котором чередуются несколько потоков вычислений, не имеет значения.Таким образом, две программы эквивалентны, если они выполняют по существу одинаковые вычисления, но в несколько ином порядке.Вы можете сделать модель параллельных вычислений из модели последовательных вычислений, взглянув на наборы возможных перемежений вместо отдельных прогонов программы, но это добавляет уровень косвенности, которым трудно управлять.Следовательно, большинство моделей параллелизма обжигают недетерминизм в систему.Когда вы сделаете это, вы больше не сможете работать на машине Тьюринга .
¹ В этом отношении мысль (что происходит в нашем мозгу) все еще остается магией вощущение, что мы понятия не имеем, как это делается, у нас нет научного понимания этого.Все, что мы умеем воспроизводить (не в биологическом смысле!), Вычислимо по Тьюрингу.
² Обратите внимание, что здесь язык включает в себя все, что вы не можете определить самостоятельно.В этом смысле стандартная библиотека является частью «языка».