patternCritical
Can a computer determine whether a mathematical statement is true or not?
Viewed 0 times
canstatementtruecomputerdeterminewhethermathematicalnot
Problem
I was reading Introduction to the Theory of Computation by Michael Sipser and I found the following paragraph quite interesting:
During the first half of the twentieth century, mathematicians such as Kurt
Godel, Alan Turing, and Alonzo Church discovered that certain basic problems ¨
cannot be solved by computers. One example of this phenomenon is the problem of determining whether a mathematical statement is true or false. This task
is the bread and butter of mathematicians. It seems like a natural for solution
by computer because it lies strictly within the realm of mathematics. But no
computer algorithm can perform this task.
Among the consequences of this profound result was the development of ideas
concerning theoretical models of computers that eventually would help lead to
the construction of actual computers
As a CS student, completely new to the theory of computation, this is hard to believe for me. It said that a computer can't solve a basic task such as determining whether a mathematical statement is true or false. Can't it really!? I have programmed lots of codes that determine if a mathematical statement is true or not. For example, a simple code such as
I'm sure I'm missing something here. Perhaps I'm mistaken by the definition of "Mathematical statement".
But I'm quite sure "Is 6 equal to 2 * 3?" is a mathematical statement and can be validated by a computer.
So what did the text mean by that? I'm confused!
PS: Sorry if the Complexity theory tag is misplaced here. As I said I'm new to the field and on the same page the author of the book stated that the theories of computability and complexity are closely related.
During the first half of the twentieth century, mathematicians such as Kurt
Godel, Alan Turing, and Alonzo Church discovered that certain basic problems ¨
cannot be solved by computers. One example of this phenomenon is the problem of determining whether a mathematical statement is true or false. This task
is the bread and butter of mathematicians. It seems like a natural for solution
by computer because it lies strictly within the realm of mathematics. But no
computer algorithm can perform this task.
Among the consequences of this profound result was the development of ideas
concerning theoretical models of computers that eventually would help lead to
the construction of actual computers
As a CS student, completely new to the theory of computation, this is hard to believe for me. It said that a computer can't solve a basic task such as determining whether a mathematical statement is true or false. Can't it really!? I have programmed lots of codes that determine if a mathematical statement is true or not. For example, a simple code such as
return 6 == 2*3 will return true if this statement is true, so why does the text says that a computer can't perform this task?I'm sure I'm missing something here. Perhaps I'm mistaken by the definition of "Mathematical statement".
But I'm quite sure "Is 6 equal to 2 * 3?" is a mathematical statement and can be validated by a computer.
So what did the text mean by that? I'm confused!
PS: Sorry if the Complexity theory tag is misplaced here. As I said I'm new to the field and on the same page the author of the book stated that the theories of computability and complexity are closely related.
Solution
The claim is not that a computer cannot determine the validity of some mathematical statements. Rather, the claim is that there is a class $\mathcal{C}$ of mathematical statements such that no algorithm can decide, given a statement from class $\mathcal{C}$, whether it is valid or not.
The standard choice for the class $\mathcal{C}$ is statements about natural numbers, for example:
Every even integer greater than two is a sum of two primes.
The class $\mathcal{C}$ contains all statements of the form:
For all natural $n_1$ there exists natural $n_2$ such that for all natural $n_3$ there exists natural $n_4$ such that ... there exists natural $n_{2m}$ such that $P(n_1,\ldots,n_{2m})$,
where $P$ is an expression using logical operators, comparison operators, addition, subtraction, multiplication, division, and integer constants.
Another popular choice for the class $\mathcal{C}$ is:
The following algorithm halts: ...
In both cases, there is no algorithm that takes an arbitrary statement from class $\mathcal{C}$ and correctly outputs whether the statement is valid or not.
It is crucial that the algorithm be required to answer correctly for all statements in $\mathcal{C}$. We can easily write an algorithm that answers correctly on a single statement from $\mathcal{C}$. Indeed, one of the following algorithms will work:
The statement is valid.
The statement is not valid.
Similarly, we can design an algorithm that answers correctly on two different statements $A,B$. One of the following will work:
The statement is valid.
The statement is not valid.
If the statement is $A$, then it is valid, otherwise it is not valid.
If the statement is $B$, then it is valid, otherwise it is not valid.
We cannot implement this strategy in the case of infinitely many statements, since an algorithm, by definition, has a finite description. This is the hard part – being able to decide, for infinitely many statements, whether they are valid or not.
The standard choice for the class $\mathcal{C}$ is statements about natural numbers, for example:
Every even integer greater than two is a sum of two primes.
The class $\mathcal{C}$ contains all statements of the form:
For all natural $n_1$ there exists natural $n_2$ such that for all natural $n_3$ there exists natural $n_4$ such that ... there exists natural $n_{2m}$ such that $P(n_1,\ldots,n_{2m})$,
where $P$ is an expression using logical operators, comparison operators, addition, subtraction, multiplication, division, and integer constants.
Another popular choice for the class $\mathcal{C}$ is:
The following algorithm halts: ...
In both cases, there is no algorithm that takes an arbitrary statement from class $\mathcal{C}$ and correctly outputs whether the statement is valid or not.
It is crucial that the algorithm be required to answer correctly for all statements in $\mathcal{C}$. We can easily write an algorithm that answers correctly on a single statement from $\mathcal{C}$. Indeed, one of the following algorithms will work:
The statement is valid.
The statement is not valid.
Similarly, we can design an algorithm that answers correctly on two different statements $A,B$. One of the following will work:
The statement is valid.
The statement is not valid.
If the statement is $A$, then it is valid, otherwise it is not valid.
If the statement is $B$, then it is valid, otherwise it is not valid.
We cannot implement this strategy in the case of infinitely many statements, since an algorithm, by definition, has a finite description. This is the hard part – being able to decide, for infinitely many statements, whether they are valid or not.
Context
StackExchange Computer Science Q#135343, answer score: 76
Revisions (0)
No revisions yet.