10.2 The Universal Function

Question 1

What is the universal function

Answer 1

A function which can reproduce the behaviour of any other computable function

Question 2

What is Kleene’s theorem

Answer 2

The universal function is computable

Function must be in form f: N->N to be computable.

Question 3

How does program that computes the universal function work

Answer 3

• Decodes input
• Runs each line of while AST
• Similar to interpreter