Fun Tasks
# Can Robots Take Over the World?

#### Join our exclusive online lessons today!

Is it possible for machines, robots, or computers to assume global dominance? Let's explore this scenario, specifically when machines possess the capability to solve any problem, including mathematical ones. In such a scenario, it becomes theoretically plausible for machines to take control. For instance, robots might outperform humans in locating energy sources for their sustenance.

Fortunately, machines do have limitations, even when it comes to solving mathematical problems. Two principal arguments stem from mathematical logic and proof theory. First, there's Gödel's incompleteness theorem (also known as the first Gödel's theorem). This theorem asserts the existence of a true mathematical statement that can never be proven. It might sound astonishing that something true remains unproven. Our common intuition often equates truth with provability. However, in mathematics, truth is defined more flexibly: everything provable is true, but not everything true is provable.

Let's delve into how Gödel's incompleteness theorem was established—how a true yet unprovable statement was unearthed. To begin, let's consider what constitutes a proof. When proving a theorem, we commence with initial true statements known as axioms. We employ logic to derive new true statements. This process continues, creating a set of true statements, which is termed a theory. All statements within a theory, including axioms, are referred to as theorems. For example, the set of all geometric theorems constitutes a theory.

Similarly, number theory comprises true assertions concerning natural numbers, addition, and multiplication. However, a theory may not encompass all possible statements. It’s useful to recall the Fibonacci sequence here. We start from 1, 1 taking the sum of the two preceding elements as the next element of our sequence. Thus, we have 1, 1, 2, 3, 5, 8, 13, ….

When we prove theorems starting from a set of axioms, some statements remain outside our theory—they go unproven. Gödel demonstrated that for certain statements A concerning natural numbers, neither A nor its negation, not-A, can be proven within number theory. Since one of these statements must be true, number theory fails to encompass certain true statements. In essence, there are true statements about natural numbers that cannot be proven.

The second argument addresses true statements that are theoretically provable but demand an extensive amount of time for proof. To illustrate, imagine a formal grammar with two rules:

S → abS

S → ϵ

These rules dictate how the grammar functions. We begin with S and apply either rule 1 or rule 2, substituting S in the string accordingly. The symbol ϵ in rule 2 signifies the removal of S. For instance, applying rule 1 four times yields:

S → abS → ababS → abababS → ababab

This grammar generates all strings in the form (ab)^{n}, such as (ab)^{2} = abab and (ab)^{5} = ababababab. In particular, it can generate exceedingly lengthy strings like (ab)^{1,000,000,000,000}. However, how much time would a computer require to generate these lengthy strings? A comparable situation arises in theorem proving: some theorems are provable but necessitate timeframes that surpass the lifespan of our universe.

Consequently, we encounter true statements that remain unproven and true statements that, while provable in principle, evade proof due to their protracted nature.

Private Lessons | | | Group Lessons |