Theory of computation | Functions and mappings | Computability theory | Recursion

Primitive recursive function

In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined before entering the loop). Primitive recursive functions form a strict subset of those general recursive functions that are also total functions. The importance of primitive recursive functions lies in the fact that most computable functions that are studied in number theory (and more generally in mathematics) are primitive recursive. For example, addition and division, the factorial and exponential function, and the function which returns the nth prime are all primitive recursive. In fact, for showing that a computable function is primitive recursive, it suffices to show that its time complexity is bounded above by a primitive recursive function of the input size. It is hence not that easy to devise a computable function that is not primitive recursive; some examples are shown in section below. The set of primitive recursive functions is known as PR in computational complexity theory. (Wikipedia).

Video thumbnail

Recursive Functions (Discrete Math)

This video introduces recursive formulas.

From playlist Functions (Discrete Math)

Video thumbnail

Recursive Factorial Function

Introduction to recursion.

From playlist Computer Science

Video thumbnail

Comparing Iterative and Recursive Factorial Functions

Comparing iterative and recursive factorial functions

From playlist Computer Science

Video thumbnail

Recursively Defined Sets - An Intro

Recursively defined sets are an important concept in mathematics, computer science, and other fields because they provide a framework for defining complex objects or structures in a simple, iterative way. By starting with a few basic objects and applying a set of rules repeatedly, we can g

From playlist All Things Recursive - with Math and CS Perspective

Video thumbnail

Applying the recursive formula to a sequence to determine the first five terms

👉 Learn all about recursive sequences. Recursive form is a way of expressing sequences apart from the explicit form. In the recursive form of defining sequences, each term of a sequence is expressed in terms of the preceding term unlike in the explicit form where each term is expressed in

From playlist Sequences

Video thumbnail

How to use the recursive formula to evaluate the first five terms

👉 Learn all about recursive sequences. Recursive form is a way of expressing sequences apart from the explicit form. In the recursive form of defining sequences, each term of a sequence is expressed in terms of the preceding term unlike in the explicit form where each term is expressed in

From playlist Sequences

Video thumbnail

Applying the recursive formula to a geometric sequence

👉 Learn all about recursive sequences. Recursive form is a way of expressing sequences apart from the explicit form. In the recursive form of defining sequences, each term of a sequence is expressed in terms of the preceding term unlike in the explicit form where each term is expressed in

From playlist Sequences

Video thumbnail

Using the recursive formula to find the first four terms of a sequence

👉 Learn all about recursive sequences. Recursive form is a way of expressing sequences apart from the explicit form. In the recursive form of defining sequences, each term of a sequence is expressed in terms of the preceding term unlike in the explicit form where each term is expressed in

From playlist Sequences

Video thumbnail

Foundations - Seminar 10 - Gödel's incompleteness theorem Part 2

Billy Price and Will Troiani present a series of seminars on foundations of mathematics. In this seminar Will Troiani continues with the proof of Gödel's incompleteness theorem, providing some background on general recursive functions. You can join this seminar from anywhere, on any devic

From playlist Foundations seminar

Video thumbnail

Foundations - Seminar 11 - Gödel's incompleteness theorem Part 3

Billy Price and Will Troiani present a series of seminars on foundations of mathematics. In this seminar Will Troiani continues with the proof of Gödel's incompleteness theorem, discussing Gödel's beta function and the role of the Chinese Remainder theorem in the incompleteness theorem. Y

From playlist Foundations seminar

Video thumbnail

Foundations - Seminar 14 - Gödel's incompleteness theorem Part 6

Billy Price and Will Troiani present a series of seminars on foundations of mathematics. In this seminar Will Troiani continues with the proof of Gödel's incompleteness theorem. You can join this seminar from anywhere, on any device, at https://www.metauni.org. This video was filmed in D

From playlist Foundations seminar

Video thumbnail

Foundations - Seminar 9 - Gödel's incompleteness theorem Part 1

Billy Price and Will Troiani present a series of seminars on foundations of mathematics. In this seminar Will Troiani starts the proof of Gödel's incompleteness theorem. You can join this seminar from anywhere, on any device, at https://www.metauni.org. This video was filmed in Deprecati

From playlist Foundations seminar

Video thumbnail

The Most Difficult Program to Compute? - Computerphile

The story of recursion continues as Professor Brailsford explains one of the most difficult programs to compute: Ackermann's function. Professor Brailsford's programs: http://bit.ly/1nhKtW4 Follow Up Film from the Prof in response to this film: https://www.youtube.com/watch?v=uNACwX-O5l

From playlist Subtitled Films

Video thumbnail

Lecture 9B: Explicit-control Evaluator

MIT 6.001 Structure and Interpretation of Computer Programs, Spring 2005 Instructor: Harold Abelson, Gerald Jay Sussman, Julie Sussman View the complete course: https://ocw.mit.edu/6-001S05 YouTube Playlist: https://www.youtube.com/playlist?list=PLE18841CABEA24090 Explicit-control Evaluat

From playlist MIT 6.001 Structure and Interpretation, 1986

Video thumbnail

Lecture 9B | MIT 6.001 Structure and Interpretation, 1986

Explicit-control Evaluator Despite the copyright notice on the screen, this course is now offered under a Creative Commons license: BY-NC-SA. Details at http://ocw.mit.edu/terms Subtitles for this course are provided through the generous assistance of Henry Baker, Hoofar Pourzand, Heath

From playlist MIT 6.001 Structure and Interpretation, 1986

Video thumbnail

GPT-4 is a Computer... I taught ChatGPT (GPT-4) the LOOP programming language

OpenAI's next generation of ChatGPT GPT-4 is not only able to learn to programming languages bug it is able to execute them. It's a computer. I taught the AI to code the LOOP programming language by Albert Meyer and Dennis Ritchie from 1967. A theoretical language that has never been i

From playlist AI

Video thumbnail

Typescript Tutorial for Beginners [ 2023 Updated ] | Learn Typescript in 2 Hours | Simplilearn

🔥Post Graduate Program In Full Stack Web Development: https://www.simplilearn.com/pgp-full-stack-web-development-certification-training-course?utm_campaign=TypescriptTutorialforBeginners-Tc0mceLJ4gQ&utm_medium=DescriptionFF&utm_source=youtube 🔥Caltech Coding Bootcamp (US Only): https://

From playlist TypeScript Training Videos

Video thumbnail

How to determine the first five terms for a recursive sequence

👉 Learn all about recursive sequences. Recursive form is a way of expressing sequences apart from the explicit form. In the recursive form of defining sequences, each term of a sequence is expressed in terms of the preceding term unlike in the explicit form where each term is expressed in

From playlist Sequences

Video thumbnail

Foundations - Seminar 12 - Gödel's incompleteness theorem Part 4

Billy Price and Will Troiani present a series of seminars on foundations of mathematics. In this seminar Will Troiani continues with the proof of Gödel's incompleteness theorem, by proving that general recursive functions are representable. You can join this seminar from anywhere, on any

From playlist Foundations seminar

Related pages

Richard Dedekind | Ackermann function | Exponentiation | Set theory | If and only if | Truth value | Undecidable problem | Primitive recursive arithmetic | Negation | Operation (mathematics) | Primitive recursive functional | Turing completeness | Monus | Indicator function | Gödel numbering | Mutual recursion | Primitive recursive set function | George Boolos | Gödel numbering for sequences | Double recursion | LOOP (programming language) | Domain of a function | Identity function | Wilhelm Ackermann | Rational number | Computable function | Factorial | Exponential function | Paris–Harrington theorem | Forcing (mathematics) | Arity | Primality test | First-order logic | Proof theory | Rózsa Péter | Division (mathematics) | Recursive definition | General recursive function | Grzegorczyk hierarchy | Sudan function | Natural number | Addition | Course-of-values recursion | Field (mathematics) | Diagonal lemma | Computability theory | Gödel's β function | PR (complexity) | Turing machine | Number theory | Subset | Halting problem | Time complexity | Axiom | ACM SIGACT | Computational complexity theory | Partial function | Thoralf Skolem | Logical conjunction | Cantor's diagonal argument | Finitism | Recursion (computer science)