2016/02/16 by Baltasar Trancón y Widemann, Widemann, Baltasar Trancón y
Computer Science · #Artificial Intelligence in Games #Computability, Logic, AI Algorithms #D.1.1 #D.3.3 #F.3.3 #F.4.1 #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #Logic, programming, and type systems #Programming Languages (cs.PL) #cs.LO #cs.PL
paper · pdf · doi:10.48550/arxiv.1602.05010
arxiv created 2016/02/16 · openalex publication_date 2016/02/16 · arxiv updated 2016/02/17 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
The Ackermann function is a famous total recursive binary function on the natural numbers. It is the archetypal example of such a function that is not primitive recursive, in the sense of classical recursion theory. However, and in seeming contradiction, there are generalized notions of total recursion, for which the Ackermann function is in fact primitive recursive, and often featured as a witness for the additional power gained by the generalization. Here, we investigate techniques for finding and analyzing the primitive form of complicated recursive functions, namely also Knuth's and Conway's arrow notations, in particular by recursion abstraction, in a framework of functional program transformation.