21
$\begingroup$

I know that, in imperative programming languages, a while-do loop is sufficient as a control flow construct to make the language Turing-complete (as far as control flow goes - of course we also need unbounded memory and certain operators...). The gist of my question is: does a do-while loop have the same computational power as a while-do loop? In other words, can a language be Turing-complete if it's impossible to skip instructions entirely.

I realise that some of the semantics here could be a bit ambiguous, so let me phrase the actual question with a specific example:

Brainfuck (BF) is a Turing tarpit where the only control flow is a while-do loop, denoted as [...] (there is a complete language spec at the bottom of the question, in case you're not familiar with Brainfuck). Let's define a new language BF*, where ,.+-<> have the same semantics as in BF, but instead of [] we have {} which denotes a do-while loop. That is, the only difference to BF is that every loop is executed at least once before further iterations can be skipped.

Is BF* Turing-complete? If it is, I'd be interested in how I could translate BF to BF*. If it isn't, how do I prove that?

Some observations of my own:

  • Not every BF program can be translated into BF*. For instance, it's impossible to write a program in BF* which may or may not read or print a value - if the program potentially prints one or more values, it will always print at least one. However, there might be a Turing-complete subset of BF which can be translated to BF*.
  • We cannot simply translate [f] (where f is some arbitrary, Brainfuck program consisting only of +-[]<>) to f-1{f} (in an attempt to cancel the effect of the first iteration), because a) not every computable function has a computable inverse and b) even if it did, f-1 wouldn't necessarily have fewer loops than f so applying this step recursively isn't guaranteed to terminate in the first place.

Here is a quick overview over the Brainfuck language. Brainfuck operates on an infinite tape where each cell contains a byte values, initially zero. Overflows wrap around, so incrementing 255 gives 0 and vice versa. The language consists of 8 instructions:

+   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 [.
$\endgroup$
  • 2
    $\begingroup$ Very similar question. $\endgroup$ – Raphael Sep 28 '15 at 0:00
  • $\begingroup$ interesting but think it is not fully carefully constructed. [] is not exactly defining a "while do" loop in BF. as in your table the left and right brackets evaluate the current cell zero/ nonzero. so what is the exact description of the corresponding {} braces evaluation logic? suggest further dialog/ discussion in Computer Science Chat. also your "observations" are more like "postulates" or "propositions" without proof. $\endgroup$ – vzn Sep 28 '15 at 22:42
  • $\begingroup$ @vzn Those are good points. I figured that the obvious definition of {} would be to make { do nothing at all and } the same as ]. I won't have much time over the next few days, but I'll join you in chat when I do find some time. $\endgroup$ – Martin Ender Sep 29 '15 at 6:14
  • $\begingroup$ so alas this is apparently somewhat subtle to ask and there seem to be two totally different questions here. (1) given any Turing complete language with a while-do loop (and "other stuff"), can it be converted to a Turing complete language with only a do-while loop instead. but then one needs to know more about the "other stuff" in detail to answer. (2) given BF and a new BF* with given definition of {} and taking away [], is BF* Turing complete. with the understanding that BF [] is a construct only something somewhat like/ analogous to a while-do loop in Turing complete languages. $\endgroup$ – vzn Sep 29 '15 at 16:35
  • 1
    $\begingroup$ @vzn part (1) was only the TL;DR part of my question. I'm fully aware that this is probably impossible to answer for "some language". This is why I've phrased the actual question in terms of a very simple toy language (BF) to really narrow it down to the behaviour of the loops (because I figured if BF* can be shown to be TC that would make it simpler to show it for other languages which only have do-while loops). I'm not sure how you think BF loops are different from other language's while-do loops though. $\endgroup$ – Martin Ender Sep 29 '15 at 17:09
10
$\begingroup$

I don't know Brainfuck so you'll have to do some translation from my pseudocode. But, assuming that Brainfuck behaves sensibly (ha!), everything below should apply.

do-while is equivalent to while-do. do X while Y is equivalent to X; while Y do X and, assuming you have conditionals, while Y do X is equivalent to if Y then (do X while Y).

Life is a bit harder if you don't have conditionals. If you have while-do, you can simulate if Y then X using something like this:

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

But what if you only have do-while? I claim that the following simulates if Y then X, assuming that X terminates given the current value of the variables. (This isn't guaranteed: the program if y=0 then loopforever terminates if y != 0, even though X loops for any value of the variables). Let V1, ..., Vn be the variables modified by X and let X' be X modified so that it uses Vi' instead of Vi for each of those variables. swap(A,B) denotes the obvious code that swaps the variables A and 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'

The idea is the following. First, suppose that Y is false. We simulate doing X once, and store the results in V1'', ..., Vn''; V1', ..., Vn' hold the original values of V1, ..., Vn. Then, we assign V1 := V1'; ...; Vn := Vn', which does nothing. So, if Y is false, we've done nothing. Now, suppose that Y is true. We'll now simulate X twice, storing the results in both the "primed" and "double-primed" variables. So, now, the assignments at the end of the loop have the effect that X was computed once. Note that Y only depends on the "unprimed" variables, so its value is not affected by running the loop repeatedly.

OK, so what if X might not terminate for the current value of the variables? (Thanks to Martin Ender for pointing out this possibility.) In that case, we need to simulate X instruction-by-instruction, using similar ideas to those above. Each instruction definitely terminates so we can use the if simulation above to do instruction decoding, along the lines of "If the opcode is foo, do this; if it's bar, do that; ...". So, now, we use a loop to iterate through the instructions of X, using an instruction pointer and so on so that we know which instruction to execute next. At the end of each iteration of the loop, check Y and check whether X has halted yet. If Y is false, the swapping technique allows us to undo the effects of X's first instruction.

$\endgroup$
  • 1
    $\begingroup$ This is a neat idea, but I think there is one issue here: consider the case where Y is false but X doesn't terminate on the current set of variable values. if Y then X terminates, but your translation doesn't, because it always needs to execute X' at least once. $\endgroup$ – Martin Ender Sep 27 '15 at 11:53
  • 1
    $\begingroup$ @MartinBüttner Urgh. You're right. So we need to use the loop to simulate X instruction-by-instruction and check Y after each instruction. Each instruction is guaranteed to terminate so everything will work. But it's a pain to write down. $\endgroup$ – David Richerby Sep 27 '15 at 11:56
  • 1
    $\begingroup$ I'm not entirely sure if it's possible to deconstruct X like that if it starts with a while loop/conditional itself. I'll have to think about this some more. $\endgroup$ – Martin Ender Sep 27 '15 at 12:43
  • $\begingroup$ Also "So, now, we use a loop to iterate through the instructions of X, using an instruction pointer and so on so that we know which instruction to execute next." I feel like this in itself might require a conditional of some sort. $\endgroup$ – Martin Ender Sep 27 '15 at 12:48
  • 1
    $\begingroup$ I'm still not entirely sure how you define "each instruction" if X' is non-linear. Would you mind including some more detail for a simple but non-trivial toy X? E.g. do (while A do B) while C? (the outer do while comes from the outer while do that we're currently translating) $\endgroup$ – Martin Ender Sep 27 '15 at 18:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.