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

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

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

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

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

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

10
задан David Titarenco 27 October 2010 в 03:30
поделиться