01b What is Computational Thinking?

Summary

In this lecture for McMaster University's Computer Science 1JC course, the instructor explores the fundamental question of computational thinking: What can and cannot be computed? The discussion highlights the theoretical limits of computation, mentioning the contributions of historical figures like Gottfried Wilhelm Leibniz, who pioneered the binary number system and mechanical calculation machines. Despite his ambitious dream of using computation to answer all questions, the lecture points out that undecidable problems, as shown by Church and Turing in 1936, prove some computational tasks are impossible. The session underscores the importance of understanding these limits in computational thinking.

Takeaways

• 😀 Computational thinking aims to understand the limits of what can and cannot be done with computing.
• 😀 There are two key questions: the theoretical limits of computing and the practical limits based on current technology.
• 😀 Not every problem can be solved computationally; some problems are inherently unsolvable by computers.
• 😀 Leibniz, a 17th-century polymath, contributed to the development of computational thinking and is often considered one of the first computer scientists and engineers.
• 😀 Gottfried Wilhelm Leibniz developed the binary number system and saw its potential for computation using only two symbols (0 and 1).
• 😀 Leibniz designed the Stepped Reckoner, a mechanical calculator capable of performing addition, subtraction, multiplication, division, and square roots.
• 😀 Despite living in the 1600s, Leibniz’s computational ideas influenced the development of mechanical calculators as late as the 1970s.
• 😀 Leibniz had a vision that computation could be used to solve any problem, including philosophical debates, through calculation and a universal language called 'characteristica universalis.'
• 😀 Leibniz proposed the 'calculus ratio senator,' a hypothetical computing device that would determine the truth or falsity of any statement expressed in his universal language.
• 😀 The limits of computation were later proven by Alan Turing and Alonzo Church in 1936, showing that some decision problems are undecidable, contradicting Leibniz's vision.

Q & A

What is the fundamental question of computational thinking introduced in the lecture?

The fundamental question is 'What can and cannot be done with computing?' This question divides into two parts: theoretical limits and practical limits of computing.

What are the two types of limits discussed in the context of computational thinking?

The two types of limits discussed are the theoretical limits, which consider what can be computed assuming ultimate size and speed of computers, and the practical limits, which focus on the capabilities of current computers.

Did the lecture confirm that there are theoretical limits to what can be computed?

Yes, the lecture confirms that not every problem can be solved computationally, meaning there are theoretical limits to what can be computed.

Who is Godfrey Leibniz, and why is he important in the context of computational thinking?

Godfrey Leibniz was a polymath from the 1600s, known for his contributions in philosophy, mathematics, and early computer science. He is particularly important in computational thinking because he developed the binary number system and designed a mechanical calculating machine.

What major contributions did Leibniz make to mathematics and computer science?

Leibniz developed calculus independently of Isaac Newton, invented the binary number system, and designed the stepped reckoner, a mechanical calculator capable of performing various arithmetic operations.

What was Leibniz's vision regarding computation and philosophy?

Leibniz envisioned that computation could be used to answer philosophical questions, such as whether there is one God or two, and he proposed a universal language to express all scientific ideas that could be verified through computation.

What is the Characteristica Universalis that Leibniz proposed?

The Characteristica Universalis was a universal language Leibniz proposed for expressing all scientific ideas. It was meant to be a symbolic language where philosophical questions could be answered through logical computation.

What was Leibniz’s proposed 'Calculus Ratiocinator'?

The Calculus Ratiocinator was a proposed device for determining the truth or falsity of statements written in the Characteristica Universalis. It would compute answers to questions like whether the sun would burn out in 100 years.

Why is Leibniz's vision of using computation to solve all problems considered impossible?

Leibniz's vision was proven impossible in 1936 by Alan Turing and Alonzo Church, who showed that there are undecidable decision problems that cannot be solved by computation.

What important breakthrough did Turing and Church achieve in 1936?

Turing and Church showed that there are undecidable decision problems, meaning that not all problems can be solved by computers. This fundamentally challenged Leibniz’s vision of using computation to answer all questions.

How did Kurt Gödel's incompleteness theorems influence the work of Turing and Church?

Turing and Church were influenced by Kurt Gödel's incompleteness theorems, which showed the limits of using proof to capture truth. These theorems laid the groundwork for understanding the limits of computation, which Turing and Church extended by demonstrating undecidable problems.