Timeline for can every program still be written without recursion or cyclic calls?

9 events

when toggle format	what		by	license	comment
May 16 at 4:57	history	edited	Doc Brown	CC BY-SA 4.0	added 233 characters in body
May 16 at 0:34	comment	added	Kaia		Presumably the sketch of the proof of halting-equivalence: Suppose we have an oracle for RECURSIVE. Given a TM, create a non-recursive TM simulator and run it with that TM as input, where after halting it immediately calls an infinitely-recursive function. This decides halting
May 15 at 22:08	comment	added	Corbin		@supercat: This is called defunctionalization. Indeed, it's known that CPS transformation followed by defunctionalization will convert general recursion into iteration.
May 15 at 21:16	comment	added	supercat		At least one C-dialect implementation I've used assumes that a call via function pointer is capable of calling any function whose signature matches the function pointer, but no other functions. Having a function pointer and all functions that should be viewed as "reachable" through it return a structure type that is used for no other purpose may break any cycles that might otherwise arise. This is a practical technique in a real implementation I've used.
May 15 at 20:04	history	edited	Doc Brown	CC BY-SA 4.0	added 96 characters in body
May 15 at 19:53	history	edited	Doc Brown	CC BY-SA 4.0	added 737 characters in body
May 15 at 19:29	history	edited	Doc Brown	CC BY-SA 4.0	edited body
May 15 at 19:12	history	edited	Doc Brown	CC BY-SA 4.0	edited body
May 15 at 16:31	history	answered	Doc Brown	CC BY-SA 4.0