vs sencilla anidada

Question

¿Son simples bucles más potente que los bucles anidados en términos de integridad de Turing?

Answer 1

En cuanto a la integridad de Turing, sí lo son.

Prueba: Es posible escribir un Brainf *** intérprete mediante un bucle sencillo, por ejemplo aquí:

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

Answer 2

Para bucles con un número fijo de pasos (LOOP, PARA y similares): Imagínese todo el propósito de un bucle es contar con n. ¿Por qué debería hacer una diferencia si los tiempos i bucle I en un número de bucles y j exteriores en un bucle interno como n = i * j opuesta en un solo bucle?

Supongamos que no WHILE, GOTO o construcciones similares están permitidos en un programa (justo asignación, IF, y bucles fijos). Entonces todos estos programas terminan después de un número finito de pasos.

El siguiente paso para más expresibilidad es permitir bucles, donde el número de iteraciones es, por ejemplo determinado por una condición, y no es seguro, si esta condición se cumple siempre (mientras, por ejemplo). Entonces es que puede suceder, que un programa no se detendrá. (Este tipo de expresividad también se conoce como Turing-completitud).

En correspondencia con estas dos formas de programas se les llama dos tipos de funciones, que se desarrollaron históricamente en torno al mismo tiempo y que recursión primitiva y funciones µ-recursivas .

El número de anidaciones no juega un papel en esto.