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

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

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

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

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

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

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