Hacker News new | ask | show | jobs
LOOP (programming language) (en.wikipedia.org)
36 points by anqurvanillapy 2737 days ago
3 comments

We are learning these (meaning LOOP, WHILE, GOTO) in university right now, the course is designed after a short German textbook of Schöning. The proofs on how powerful they are are quite interesting (e.g. you emulate the syntax of a GOTO program with WHILE statments and thus show WHILE >= GOTO). Does anybody know if these specific theoretical programming languages are of any furter/or in wide use in theoretical CS?
I don’t know about the prevalence of any of them in theoretical CS (I’m not in the field and only know about them from university), but LOOP is equivalent to primitive recursion, and WHILE is equivalent to μ-recursion. If not LOOP, WHILE and GOTO themselves, maybe the recursion are prevalent? I imagine they are a bit more convenient for proofs and the like.
How is GOTO not equivalent to WHILE? You can emulate any arbitrary flow-control construct with GOTO.
Presumably you need another proof for GOTO >= WHILE and therefore GOTO = WHILE
Exactly. You emulate every WHILE instruction with a GOTO insturction.
Even addition, subtraction, and variable assignment are unnecessary. All you need is succession:

https://esolangs.org/wiki/Restricted_BlooP/FlooP

May his next language be called Tetration