Я знаю, что в императивных языках программирования цикла 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-1
f
Вот краткий обзор языка 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. как и в вашей таблице, левая и правая скобки оценивают текущую ячейку ноль / ненулевое значение. так каково точное описание соответствующей{}
логики оценки фигурных скобок? предложить дальнейший диалог / обсуждение в информатическом чате . также ваши «наблюдения» больше похожи на «постулаты» или «предложения» без доказательств.{}
было бы{
вообще ничего не делать и так}
же, как]
. У меня не будет много времени в течение следующих нескольких дней, но я присоединюсь к вам в чате, когда найду время.{}
и удалением[]
является BF * Turing завершенным. с пониманием того, что BF[]
является конструкцией, которая является чем-то вроде / аналогичным циклу while-do в полных языках Тьюринга.Ответы:
Я не знаю 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
используя что-то вроде этого:Но что, если у вас есть только время? Я утверждаю, что следующее моделирует
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
.Идея заключается в следующем. Сначала предположим, что
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
Первая инструкция.источник
Y
ложно, ноX
не заканчивается на текущем наборе значений переменных.if Y then X
заканчивается, но ваш перевод - нет, потому что он всегда должен выполнятьсяX'
хотя бы один раз.X
инструкции за инструкцией и проверкиY
после каждой инструкции. Каждая инструкция гарантированно прекращается, поэтому все будет работать. Но это боль, чтобы записать.X
, если он начинается с цикла while / условного выражения. Я должен подумать об этом еще немного.X'
она нелинейная. Не могли бы вы добавить еще несколько деталей для простой, но нетривиальной игрушкиX
? Напримерdo (while A do B) while C
? (внешнееdo while
исходит от внешнего,while do
которое мы сейчас переводим)