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

Question

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

Чтение о немецком Z3 и ENIAC , Википедия говорит:

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

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

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

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

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

Answer 1

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

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

, а затем делаете каждое назначение a = b op c в этом разделе следующим образом:

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

(т. Е. Каждое назначение не допускается, кромев активном разделе).Теперь это все еще включает условное назначение: как сравнить 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.

Рохас также написал Условное ветвление не требуется для универсальных вычислений в фон Неймане Компьютерс .Там он предлагает машину с самоизменяющимся кодом и относительной адресацией, чтобы вы могли читать инструкции Тьюринга из памяти и модифицировать программу для соответствующего перехода.В качестве альтернативы он предлагает вышеуказанный подход (для Z3) в версии, которая использует только LOAD (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, вы можете смоделировать условные выражения. Я иногда использовал это для имитации "ON x GOTO a, b, c" в ZX Basic.

Если «true» имеет числовое значение 1, а «false» 0, то конструкция выглядит так:

if A then goto B else goto C

идентично:

goto C+(B-C)*A

Так что, да, с «вычисленным goto» или способностью к самоизменению goto или jmp могут выступать в качестве условного.

Answer 5

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

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

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

Answer 6

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

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

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

Answer 7

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