Loops in bitcoin scripting

Question

According to this Q&A there are no loops in bitcoin script: The Bitcoin scripting system is purposefully not Turing-complete - why?

I was reading the comments in a reddit post and realized few for loops could be replaced by if else statements to achieve something similar: https://www.reddit.com/r/Bitcoin/comments/rikjh0/any_one_smart_enough_to_answer_this/hoy8z52

What are the issues with this approach? Has anyone tried this?

Answer 1

You can code the loop...

for i=1 to 10
   print "Hello #",i
endfor

...as...

print "Hello #1"
print "Hello #2"
print "Hello #3"
print "Hello #4"
print "Hello #5"
print "Hello #6"
print "Hello #7"
print "Hello #8"
print "Hello #9"
print "Hello #10"

They are equivalent programs. You can do this even for complicated loops with a variable end point...

for i=1 to y
   print "Hello #",i
end for

...could be rewritten as...

if y>=1 then print "Hello #",1
if y>=2 then print "Hello #",2
if y>=3 then print "Hello #",3
...(up to the maximum possible value of y)...

This is called "loop unrolling" and you can theoretically do this for any finite loop, but as you can see in the examples above the code can get very large.

In bitcoin, the size of your script is both theoretically and practically limited in several places, so this ultimately limits the maximum number of loop iterations you can unroll in a bitcoin script, but it is possible to implement a low iteration count loop like for i=1 to 5 in bitcoin script using unrolling.

Answer 2

Loops (while loops) in this sense are meant as potentially infinite. For loops are not such loops. In other words, in what is here called for loop, one does know the number of iterations of the execution of the inner block of the loop WITHOUT inspecting the code of the inner block. In what is here called while loop this number of iterations is not known without inspecting the code of the inner block. The difference then is that in case of while loops it is in general not possible to decide whether such a loop ends or not (aka halting problem).

As Andrew mentioned above, this should not be confused with a specific syntax of some languages (i.e. where you write for keyword, it does not imply you are writing what I refer to here as for loop). If this is confusing, you can look up Pascal language and understand those types of loops as Pascal loops.

Languages that do not have while loops are not Turing complete. And Bitcoin script does not have such a loop.