Simple vs. Nested

Question

Are simple loops as powerful as nested loops in terms of Turing completeness?

Answer 1

In terms of Turing completeness, yes they are.

Proof: It's possible to write a Brainf*** interpreter using a simple loop, for example here:

http://www.hevanet.com/cristofd/brainfuck/sbi.c

Answer 2

For loops with a fixed number of steps (LOOP, FOR and similar): Imagine the whole purpose of a loop is to count to n. Why should make it a difference if I loop i times in an outer loop and j times in an inner loop as opposed n = i * j in just a single loop?

Assume that no WHILE, GOTO or similar constructs are allowed in a program (just assignment, IF, and fixed loops). Then all these programs end after a finite number of steps.

The next step to more expressibility is to allow loops, where the number of iterations is e.g. determined by a condition, and it is not sure, whether this condition is ever satisfied (e.g. WHILE). Then is may happen, that a program won't halt. (This type of expressiveness is also known as Turing-completeness).

Corresponding to these two forms of programs are two kinds of functions, which were historically developed around the same time and which are called primitive recursive functions and μ-recursive functions.

The number of nestings doesn't play a role in this.