Computer Science
Grade 11
20 min
Computability
Computability
What you'll learn
- Identify at least three different 'Looks' blocks (e.g., say, think, change size) in Scratch Jr. and describe what each one does.
- Apply 'Looks' blocks to make a character in Scratch Jr. change its appearance (e.g., change color, size, or say something) when a specific event happens (e.g., when the green flag is clicked).
- Use 'Sound' blocks to add at least one sound effect to a Scratch Jr. project and explain how the sound block makes the sound play.
- Create a short story in Scratch Jr. that uses both 'Looks' and 'Sound' blocks to make the characters talk and react to events, demonstrating understanding of how the blocks work together.
Tutorial Preview
1
Introduction & Learning Objectives
Learning Objectives
Define computability and explain its importance in computer science.
Describe the Turing Machine as a universal model of computation.
Differentiate between decidable and undecidable problems using concrete examples.
Explain the Halting Problem and its fundamental implications for programming.
Analyze a simple problem and determine if it is computable and decidable.
Relate the concept of computability to the practical limits of software development.
Can a computer program solve *any* problem you give it, as long as it's powerful enough? 🤔 Let's explore the absolute limits of what algorithms can and cannot do.
This lesson introduces the theory of computability, which asks a fundamental question: What problems can be solved by a computer? We will...
2
Key Concepts & Vocabulary
TermDefinitionExample
ComputabilityThe study of which problems can be solved using an algorithm. A problem is computable if there exists an algorithm that can solve it in a finite amount of time.The problem of sorting a list of numbers is computable because algorithms like Merge Sort or Quick Sort exist to solve it.
Turing MachineA mathematical model of computation that defines an abstract machine. It consists of an infinite tape, a head that can read and write symbols, and a set of rules. It is considered the theoretical foundation for all modern computers.A Turing machine could be designed to add two numbers. It would read the numbers from its tape, follow a set of rules to perform the addition, and write the result back onto the tape.
AlgorithmA finite, well-defined sequence of instruc...
3
Core Syntax & Patterns
The Church-Turing Thesis
Any function that can be computed by an algorithm (an 'effectively calculable' function) can be computed by a Turing Machine.
This is not a formal theorem but a foundational principle. It connects the intuitive idea of an algorithm with the formal, mathematical model of a Turing Machine. It implies that if a problem can't be solved by a Turing Machine, it can't be solved by any computer, no matter how powerful.
Proof by Contradiction for Undecidability
1. Assume a solution (an algorithm) exists for the problem. 2. Use this hypothetical algorithm to construct a new, paradoxical scenario. 3. Show that this scenario leads to a logical contradiction (e.g., something must be both true and false). 4. Conclude that the initial assumption m...
4 more steps in this tutorial
Sign up free to access the complete tutorial with worked examples and practice.
Sign Up Free to ContinueSample Practice Questions
Challenging
A programmer creates a function `smart_halts(P, I, timeout)` that runs program `P` with input `I`. If `P` halts within the `timeout` period, it returns `true`. If the timeout is reached, it returns `false`. Why does this function NOT solve the Halting Problem?
A.It can give a false negative: a program might halt just after the timeout, but the function would incorrectly report that it doesn't.
B.It can give a false positive: a program might be in an infinite loop but the function reports it halts.
C.The function itself might not halt.
D.This function actually does solve the Halting Problem.
Challenging
The proof of the Halting Problem's undecidability relies on a program being able to operate on a description of another program. This concept is known as 'programs as data'. Which of these real-world tools fundamentally relies on the same concept?
A.simple calculator application.
B.video game rendering engine.
C.compiler or an interpreter.
D.file compression utility.
Challenging
Imagine a new type of computer is invented that can solve the Halting Problem. According to the tutorial's content, what would be the MOST profound implication of this discovery?
A.All software bugs could be eliminated automatically.
B.The Church-Turing Thesis would be proven false, fundamentally changing our understanding of computation.
C.Computers would become infinitely fast.
D.All currently undecidable problems would become decidable.
Want to practice and check your answers?
Sign up to access all questions with instant feedback, explanations, and progress tracking.
Start Practicing FreeMore from Computer Science Theory
Computer Science for other grades
Frequently asked questions
What grade level is "Computability"?
Computability is a Grade 11 Computer Science lesson on ExcelOS.
What will I learn in Computability?
You'll be able to: Identify at least three different 'Looks' blocks (e.g., say, think, change size) in Scratch Jr. and describe what each one does; Apply 'Looks' blocks to make a character in Scratch Jr. change its appearance (e.g., change color….
Is "Computability" free to practice?
Yes. You can read the tutorial preview for free, and signing up for a free ExcelOS account unlocks the full tutorial and all practice questions with instant feedback.
How many practice questions are included with Computability?
This lesson includes 25 practice questions across multiple difficulty levels, each with instant feedback and explanations.