Является ли условное ветвление требованием полноты по Тьюрингу?

Question

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

Читаю о немецком Z3 и ЭНИАК, Википедия говорит:

Немецкий Z3 (показан работающим в мае 1941) был спроектирован Конрадом Цузе.Оно был первым цифровым устройством общего назначения компьютер, но это было электромеханические, а не электронный, так как в нем используются реле для всех Функции.Он вычисляется логически, используя Двоичная математика.Он был запрограммирован перфоленты, но не хватало условная ветвь.Пока не предназначено для полноты по Тьюрингу случайно была, как выяснилось в 1998 году (но для того, чтобы использовать это Полнота по Тьюрингу, сложная, умная хаки были необходимы).

Какие именно сложные и умные хаки?

Статья 1998 года, Аннотация Р.Рохас также заявляет (обратите внимание, что я не читал эту статью, это всего лишь фрагмент из IEEE):

Вычислительная машина Z3, построенная Конрад Цузе между 1938 и 1941 годами, могли выполнять только фиксированные последовательности Арифметические операции с плавающей запятой (сложение, вычитание, умножение, деление и квадрат root), закодированный на перфоленте.В Интересный вопрос, который можно задать, от взгляд на историю вычислительной техники, является ли эти операции достаточный для универсальных вычислений.В статье показано, что, по сути, один программный цикл, содержащий эти Арифметические инструкции могут имитировать любая машина Тьюринга, лента которой имеет заданного конечного размера.Это делается с помощью имитация условного ветвления и Косвенная адресация с помощью Среднее арифметическое.Z3 от Zuse - это Поэтому, по крайней мере, в принципе, как универсальные, как и современные компьютеры, которые имеют ограниченное адресное пространство.

Короче говоря, специалисты по SO, какой именно тип ветвления необходим для полноты по Тьюрингу?Если предположить, что память бесконечна, может ли язык, имеющий только goto или jmp ветвящаяся конструкция (нет if или jnz конструкции) считаться полными по Тьюрингу?

Answer 1

Оригинальная бумага Rojas можно найти здесь. Отказ Основная идея состоит в том, что Z3 поддерживает только безусловный единственный цикл (приклеив концы инструкции ленты вместе). Вы создаете условное выполнение его, поместив все разделы кода один за другим в цикле и имеющие переменную Z, которая определяет, какой раздел для выполнения. В начале раздела J вы устанавливаете

 if (z==j) then t=0 else t=1

а затем сделайте каждое задание a = b op c В этом разделе прочитано

 a = a*t + (b op c)*(1-t)

(т.е. каждое назначение представляет собой NO-OP, кроме как в активном разделе). Теперь это все еще включает в себя условное задание: как сравнить z == j? Он предлагает использовать двоичное представление Z (Z1..zm) наряду с отрицательным двоичным представлением j (C1..cm), а затем вычислить

t = 1 - sqr((c1-z1)(c2-z2)...(cm-zm))

Этот продукт будет 1 только тогда, когда C и Z отличаются со всеми битами, что произойдет только в том случае, если z == j. Назначение Z (которое по существу является косвенным прыжком), также должен назначать z1..zm.

Рохас также написал Условное ветвление не требуется для универсальных вычислений в компьютерах Von Neumann. Отказ Там он предлагает машину с самомодиторным кодом и относительным адресом, так что вы можете прочитать инструкции Turging из памяти и изменять программу, чтобы соответственно прыгать. В качестве альтернативы он предлагает приведенный выше подход (для Z3) в версии, которая использует только нагрузку (A), Store (A), Inc и Dec.

Answer 2

Если у вас есть только арифметические выражения, вы можете использовать некоторые свойства арифметических операций. Например, есть A либо 0, либо 1 в зависимости от некоторого состояния (который ранее вычисляется), то A*B+(1-A)*C вычисляет выражение if A then B else C.

Answer 3

Вам нужно что-то, что может венять в ветку (результаты) ввода.

Один из способов моделирования условных ветвей состоит в том, что с самоможенным кодом - вы вычисляете вычисление, которое откладывает его результат в поток выполнения инструкций. Вы можете поставить операционный код для безоговорочного перехода в поток инструкций и выполнить математику на входе для создания правильной цели для этого прыжка, в зависимости от некоторого набора условий для ввода. Например, вычитайте x из y, сдвиньте направо на 0 - заполните, если он был положительным или 1-заполните, если он был отрицательным, затем добавьте базовый адрес и сохраните этот результат сразу после оператора JMP. Когда вы добираетесь до этого JMP, вы перейдете к одному адресу, если x == y, а другой, если x! = Y.

Answer 4

Если вы можете вычислить адрес для вашего goto или jmp, вы можете имитировать арбритарные условные условия. Я иногда использовал это для симуляции «на X Goto A, B, C» в ZX Basic.

Если «True» имеет числовое значение 1 и «ложь» 0, то конструкция, как:

if A then goto B else goto C

идентичен:

goto C+(B-C)*A

Итак, да, с «вычисленным GOTO» или способностью самостоятельно модифицировать, хоть или JMP может выступать в качестве условного.

Answer 5

Z3 был только Turing с абстрактной точки зрения. Вы можете иметь произвольно длинную программу ленты и просто вычислить обе стороны каждой условной ветви. Другими словами, для каждой ветки он вычислял бы оба ответа, и скажут вам, кто игнорирует. Очевидно, что это создает экспоненциально большие программы для каждой условной ветви, который вы бы имели, поэтому вы никогда не сможете использовать эту машину в Turging-Class.

Answer 6

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

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

Дело в том, что машина Тьюринга обеспечивает условное ветвление, поэтому то, что вы в любом случае делаете, доказывая полноту по Тьюрингу, в некоторой степени реализует условное ветвление.Приходится делать это без условного разветвления в какой-то момент, будь то камни или PN-переходы в полупроводниках.

Answer 7

Если машина может вешать, то да, это считается завершенным.

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

Обработка - это просто процесс идентификации входов в целях выбора выходов.

Разветвление - это один из способов ментализации этого процесса, состояние прыжка - это то, что может классифицировать входы, место вашего ветви, чтобы сохранить правильный вывод для этого ввода.

Так что наконец, чтобы уточнить вещи:

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