Loading the lesson
Loading the lesson
Search AllRounder.ai
Search the courses, subjects, tracks, games and features, or jump straight to a page.
Search the courses, subjects, tracks, games and features, or jump straight to a page.
Learn it your way
A short class with Sarah and her students. The other ways are under More.
Sign up free to listen. Transcripts are free to read.
Today, we will discuss computable functions. A function is called computable if you can write a program that computes its output for any valid input. Do you understand this concept?
So, if I can write a program for a function, it's computable?
Exactly! The main focus is whether such a program exists, not how long it takes to run. Let’s remember this with the acronym 'P.O.W.E.R' - Program Outputs When Existence Result.
That acronym is helpful! But what if the function is complex?
Good question! Complexity doesn’t matter. If you can write any program that consistently gives output for every input, it’s computable. Let’s move on to uncomputable functions.
Now, let's dive into uncomputable functions. What do you think an uncomputable function is?
Is it a function that we can't write a program for?
Exactly! No program will provide the output for every possible input. This leads us to an important proof: there exist such uncomputable functions.
How do we prove that uncomputable functions exist?
Great question! We’ll show that there are more possible functions than there are valid programs. Remember Cantor's diagonalization argument - it will be key in our proof!
Let’s explore cardinality now. We know the set of valid programs is countable. However, can anyone tell me the cardinality of functions from integers to a finite set?
I think it’s uncountable?
Correct! The set of all functions from positive integers to a finite set is uncountable. This proves that there are uncomputable functions.
So every program only computes one function from that uncountable set?
Exactly! That’s the crux of it. If there are more functions than programs, some will inevitably remain uncomputable.
Functions for which a program exists to compute values for every input.
Functions that cannot be computed with any program regardless of resources.
The measure of the size of a set and its implications for counting elements.
The distinction between sets that can be enumerated and those that cannot.
An example of a computable function is the function that calculates the sum of two numbers, as a program can be easily written for any inputs.
An example of an uncomputable function is the Halting Problem, where no program can determine if another program will finish running or loop indefinitely.
Computable functions, oh what a deal, programs for all, they make output real.
Imagine a wise wizard representing computable functions who can conjure answers to any question, while an uncomputable wizard remains puzzled, unable to solve certain mysteries no matter how many spells he tries.
For Remembering Types of Functions: 'C' for Computable with a 'P' (program) and 'U' for Uncomputable with 'No P' (no program can solve it).
C.U., Computable or Uncomputable — that's the cue!
Term
What is a computable function?
Click to flip
Term
What is an uncomputable function?
Click to flip
A function for which there exists a computer program that produces an output for every possible input.
A function for which no program can be written that provides outputs for every input.
A measure of the size of a set, indicating how many elements it contains.
A set that can be put into a one-to-one correspondence with the natural numbers.
A set that cannot be put into a one-to-one correspondence with the natural numbers.
This section explores the concepts of computable and uncomputable functions, demonstrating the existence of uncomputable functions through cardinality arguments.
In this section, the distinction between computable and uncomputable functions is clarified. It establishes that while all valid programs in a programming language are countable, the set of all possible functions from positive integers to a finite set is uncountable, thereby proving that uncomputable functions exist.
In this section, we delve into the idea of computable and uncomputable functions, focusing on their cardinalities. We begin by classifying a function as computable if there exists a corresponding computer program that yields outputs for every input from its domain, regardless of the efficiency of that program. Contrastingly, uncomputable functions, for which no program can provide outputs for every input, exist. We utilize Cantor's diagonalization argument to illustrate that the set of all valid programs is countable, yet the set of all functions from positive integers to a finite set is uncountable. Hence, this disparity in cardinalities confirms the existence of uncomputable functions, emphasizing the limitations of computation in theoretical computer science.