Достаточно ли цикла do-while для полноты по Тьюрингу?

22

Я знаю, что в императивных языках программирования цикла while-do достаточно в качестве конструкции потока управления, чтобы сделать язык Тьюринга завершенным (что касается потока управления - конечно, нам также нужна неограниченная память и некоторые операторы ...) , Суть моего вопроса такова: имеет ли цикл do-while ту же вычислительную мощность, что и цикл while-do? Другими словами, может ли язык быть полным по Тьюрингу, если невозможно полностью пропустить инструкции.

Я понимаю, что некоторая семантика здесь может быть немного двусмысленной, поэтому позвольте мне сформулировать реальный вопрос на конкретном примере:

Brainfuck (BF) - это тарпит Тьюринга, где единственным потоком управления является цикл while-do, обозначенный как [...](в конце вопроса есть полная языковая спецификация, если вы не знакомы с Brainfuck). Давайте определим новый язык BF *, который ,.+-<>имеет ту же семантику, что и в BF, но вместо этого []мы имеем {}обозначение цикла do-while. То есть единственное отличие от BF состоит в том, что каждый цикл выполняется по крайней мере один раз, прежде чем можно будет пропустить дальнейшие итерации.

Является ли BF * Turing-complete? Если это так, мне было бы интересно, как я могу перевести BF на BF *. Если это не так, как мне доказать это?

Некоторые мои собственные наблюдения:

  • Не каждая программа BF может быть переведена на BF *. Например, невозможно написать программу на языке BF *, которая может или не может читать или печатать значение - если программа потенциально печатает одно или несколько значений, она всегда будет печатать хотя бы одно. Однако может существовать полное по Тьюрингу подмножество BF, которое можно перевести в BF *.
  • Мы не можем просто перевести [f](где fпроизвольная программа Brainfuck состоит только из +-[]<>) в (в попытке отменить эффект первой итерации), потому что а) не каждая вычислимая функция имеет вычислимую обратную и б), даже если бы она имела, не обязательно иметь меньше циклов, чем рекурсивное, поэтому применение этого шага не гарантированно завершится.f-1{f}f-1f

Вот краткий обзор языка Brainfuck. Brainfuck работает на бесконечной ленте, где каждая ячейка содержит байтовые значения, изначально равные нулю. Переполнения оборачиваются вокруг, поэтому приращение 255 дает 0 и наоборот. Язык состоит из 8 инструкций:

+   Increment the current cell.
-   Decrement the current cell.
>   Move tape head to the right.
<   Move tape head to the left.
,   Input a character from STDIN into the current cell.
.   Output the current cell as a character to STDOUT.
[   If the current cell is zero, jump past the matching ].
]   If the current cell is non-zero, jump back to just behind the matching [.
Мартин Эндер
источник
интересно, но думаю, что он не полностью тщательно построен. []точно не определяет цикл "пока делай" в BF. как и в вашей таблице, левая и правая скобки оценивают текущую ячейку ноль / ненулевое значение. так каково точное описание соответствующей {}логики оценки фигурных скобок? предложить дальнейший диалог / обсуждение в информатическом чате . также ваши «наблюдения» больше похожи на «постулаты» или «предложения» без доказательств.
Vzn
@vzn Это хорошие моменты. Я подумал, что очевидным определением {}было бы {вообще ничего не делать и так }же, как ]. У меня не будет много времени в течение следующих нескольких дней, но я присоединюсь к вам в чате, когда найду время.
Мартин Эндер
так что, увы, это, по-видимому, довольно трудно задать, и здесь, похоже, есть два совершенно разных вопроса. (1) При наличии любого полного языка Тьюринга с циклом while-do (и «другими вещами») его можно преобразовать в полный язык Turing с использованием только цикла do-while. но тогда нужно больше узнать о «других вещах», чтобы ответить. (2) данный BF и новый BF * с заданным определением {}и удалением []является BF * Turing завершенным. с пониманием того, что BF []является конструкцией, которая является чем-то вроде / аналогичным циклу while-do в полных языках Тьюринга.
vzn
1
@vzn часть (1) была только частью TL; DR моего вопроса. Я полностью осознаю, что это, вероятно, невозможно ответить за «некоторый язык». Вот почему я сформулировал реальный вопрос в терминах очень простого игрушечного языка (BF), чтобы действительно сузить его до поведения циклов (потому что я подумал, что если BF * можно показать как TC, что сделает его проще показать его для других языков, которые имеют только циклы do-while. Я не уверен, что вы думаете, что циклы BF отличаются от циклов while-do других языков.
Мартин Эндер,

Ответы:

10

Я не знаю Brainfuck, поэтому вам придется сделать перевод из моего псевдокода. Но, предполагая, что Brainfuck ведет себя разумно (ха!), Все нижеприведенное должно применяться.

do-while эквивалентно while-do. do X while Yэквивалентно X; while Y do Xи, если у вас есть условия, while Y do Xэквивалентно if Y then (do X while Y).

Жизнь немного сложнее, если у вас нет условностей. Если у вас есть while-do, вы можете смоделировать, if Y then Xиспользуя что-то вроде этого:

B := true
while (Y and B) do
    X
    B := false
endwhile

Но что, если у вас есть только время? Я утверждаю, что следующее моделирует if Y then X, предполагая, что Xзавершается с учетом текущего значения переменных. (Это не гарантируется: программа if y=0 then loopforeverзавершается, если y != 0, даже если Xциклы для любого значения переменных). Позвольте V1, ..., Vnпеременные, измененные Xи пусть X'будут Xизменены, так что он использует Vi'вместо Viкаждой из этих переменных. swap(A,B)обозначает очевидный код, который меняет местами переменные Aи B.

V1' := V1; ...; Vn' := Vn
V1'' := V1; ...; Vn'' := Vn
C := 0
do
    X'
    swap (V1',V1''); ...; swap (Vn',Vn'')
    C := C+1
while Y and C<2
V1 := V1'; ...; Vn := Vn'

Идея заключается в следующем. Сначала предположим, что Yэто неверно. Мы моделируем выполнение Xодин раз и сохраняем результаты в V1'', ..., Vn''; V1', ..., Vn'держите исходные значения V1, ..., Vn. Затем мы назначаем V1 := V1'; ...; Vn := Vn', который ничего не делает. Итак, если Yложно, мы ничего не сделали. Теперь предположим, что Yэто правда. Теперь мы будем симулировать X дважды , сохраняя результаты как в «загрунтованных», так и в «дважды загрунтованных» переменных. Итак, теперь назначения в конце цикла имеют эффект, который Xбыл вычислен один раз. Обратите внимание, что это Yзависит только от переменных, которые не являются первоочередными, поэтому на их значение не влияет многократный запуск цикла.

Хорошо, а что если Xне может завершиться для текущего значения переменных? (Спасибо Мартину Эндеру за указание на эту возможность.) В этом случае нам нужно смоделировать Xинструкцию за инструкцией, используя идеи, аналогичные приведенным выше. Каждая инструкция определенно завершается, поэтому мы можем использовать приведенную ifвыше симуляцию для декодирования инструкций в соответствии со строкой «Если код операции foo, сделайте это; если это bar, сделайте это; ...». Итак, теперь мы используем цикл для итерации по инструкциям X, используя указатель инструкций и так далее, чтобы мы знали, какую инструкцию выполнить дальше. В конце каждой итерации цикла проверяйте Y, Xне остановился ли еще. Если Yложно, метод обмена позволяет нам отменить эффектыXПервая инструкция.

Дэвид Ричерби
источник
1
Это хорошая идея, но я думаю, что здесь есть одна проблема: рассмотрим случай, когда Yложно, но Xне заканчивается на текущем наборе значений переменных. if Y then Xзаканчивается, но ваш перевод - нет, потому что он всегда должен выполняться X'хотя бы один раз.
Мартин Эндер,
1
@ MartinBüttner Urgh. Вы правы. Поэтому нам нужно использовать цикл для имитации Xинструкции за инструкцией и проверки Yпосле каждой инструкции. Каждая инструкция гарантированно прекращается, поэтому все будет работать. Но это боль, чтобы записать.
Дэвид Ричерби,
1
Я не совсем уверен, можно ли так деконструировать X, если он начинается с цикла while / условного выражения. Я должен подумать об этом еще немного.
Мартин Эндер
Также: «Итак, теперь мы используем цикл для итерации инструкций X, используя указатель инструкций и так далее, чтобы мы знали, какую инструкцию выполнить следующей». Я чувствую, что это само по себе может потребовать какого-то условия.
Мартин Эндер,
1
Я до сих пор не совсем уверен, как вы определяете «каждую инструкцию», если X'она нелинейная. Не могли бы вы добавить еще несколько деталей для простой, но нетривиальной игрушки X? Например do (while A do B) while C? (внешнее do whileисходит от внешнего, while doкоторое мы сейчас переводим)
Мартин Эндер,