News for hackers. Stuff that matters.
Re:LOOP (programming language) by niklasd on Tuesday December 25, 2018 @07:34PM (#18759814)
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?
Re:LOOP (programming language) by anyfoo on Tuesday December 25, 2018 @08:57PM (#18760018)
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.
Re:LOOP (programming language) by xenadu02 on Wednesday December 26, 2018 @01:38AM (#18760976)
How is GOTO not equivalent to WHILE? You can emulate any arbitrary flow-control construct with GOTO.
Re:LOOP (programming language) by sullyj3 on Wednesday December 26, 2018 @03:40AM (#18761288)
Presumably you need another proof for GOTO >= WHILE and therefore GOTO = WHILE
Re:LOOP (programming language) by niklasd on Wednesday December 26, 2018 @04:11AM (#18761357)
Exactly. You emulate every WHILE instruction with a GOTO insturction.