Theory of computation: LINKS

• Turing, Church, Gödel, Computability, Complexity and Randomization: A Personal View - video lectures by Michael O. Rabin, Harvard University, 2012 http://videolectures.net/turing100_rabin_turing_church_goedel/ The [above named] have innovated the concept of computability in the 1930's. Alan Turing gave his definition of computability via a creation of a model of a universal stored program computer. The distinction between computable and non-computable functions was subsequently refined by a discussion of the inherent complexity of computable functions. The speaker will draw from his personal interaction with Church, Gödel and the people working with John von-Neumann a picture of the evolution of computing as well as give a perspective of the future of computer science and technology. 🎓🎬⭐⭐⭐

• Course at Brown Uni, by John E. Savage 🎓⭐⭐⭐ CSCI 1010 Theory of Computation https://cs.brown.edu/courses/csci1010/index.html

• https://jtobin.io/practical-recursion-schemes

• Recursive Function Theory https://legacy.earlham.edu/~peters/courses/logsys/recursiv.htm

• 5 videos about PRF "red background" 🎬⭐⭐⭐ https://www.youtube.com/watch?v=yaDQrOUK-KY&list=PLC-8dKj3F0NUnR8LeBGH3utAI9aQjFbi5

• Definitions of Computable https://www.csee.umbc.edu/~squire/reference/computable.shtml

• https://www.geeksforgeeks.org/churchs-thesis-for-turing-machine/

Recursive Functions https://plato.stanford.edu/entries/recursive-functions/

Automata theory https://cs.stanford.edu/people/eroberts/courses/soco/projects/2004-05/automata-theory/basics.html

What is the difference between total recursive and primitive recursive functions https://math.stackexchange.com/questions/75296/what-is-the-difference-between-total-recursive-and-primitive-recursive-functions

Total Recursive Functions and Partial Recursive Functions in Automata https://www.geeksforgeeks.org/total-recursive-functions-and-partial-recursive-functions-in-automata/

Recursive Function @oxford reference https://www.oxfordreference.com/view/10.1093/oi/authority.20110803100408692?rskey=n0cF6u&result=3

Computability: diagonalisation for primitive recursive functions http://web.mat.bham.ac.uk/R.W.Kaye/computability/diagforprmachines-exs.html

Recursive Function https://mathworld.wolfram.com/RecursiveFunction.html

General Recursive Function https://mathworld.wolfram.com/GeneralRecursiveFunction.html

Minsky machine https://esolangs.org/wiki/Minsky_machine

Generalized Minsky machine https://esolangs.org/wiki/Generalized_Minsky_machine

PDF Books and slides

Notes on Recursion Theoryby Yurii Khomskii 📙 https://www.math.uni-hamburg.de/home/khomskii/recursion/Recursion.pdf

The Representability of Partial Recursive Functions in Arithmetical Theories and Categories 📙 https://www.mta.ca/~rrosebru/FMCS2018/Slides/Steimle.pdf

General Models of Computation 📙 https://homeweb.csulb.edu/~tebert/teaching/lectures/419-519/gmc/gmc.pdf

Computability and Recursion - Robert Soare 📙 https://people.cs.uchicago.edu/~soare/History/compute.pdf

The Theory of Recursive Functions, Approaching its Centennial 📙 https://www.ams.org/journals/bull/1981-05-01/S0273-0979-1981-14920-X/S0273-0979-1981-14920-X.pdf