Prev: reducibility-and-gödel Next: complexity
Godel published an incompleteness theorem as well as a completeness theorem.
There are three things to distinguish them:
The completeness theory equates provability with entailment. Thus, if something is logically entailed by the set of axioms, then it is also provable from said axioms. The incompleteness theorem differentiates entailement from truth. There is no set of axioms that captures all and only the true statements about the integers. Any set of axioms that does, will also describe other universes, and if it is true for the integers but not other universes, it won’t be provable.
There are some actual questions where it is required to prove a statement like G(F) without it being proved in F itself.
Cantor also had a question if there was any infinity in size between the real numbers and that of integers. He formulated the Continuum hypothesis stating that there is no set strictly between that of the integers and the real numbers.
Godel showed that the Continuum Hypothesis can be assumed consistently. Cohen in 1963 proved that you can assume the Continuum Hypothesis is false without introducing inconsistency.
The dream of computing would be to realize “Artificial Intelligence”, or a machine that can think like humans can.
Turing proposed a criterion called the Turing Test to distinguish between humans and machines. If a human interacting with a machine cannot reliably distinguish it from a human, then the machine ought to be regarded as intelligent, just like a human.
This is probably a sufficient but not necessary condition for intelligence, since many people believe AIs are actually human.
Searle’s experiment involves locking Searle into a room where a person inserts slips of Chinese characters, and Searle has a textbook inside the box that can translate the chinese into chinese, and respond. Thus, Searle could fake speaking Chinese without understanding Chinese.
One rebuke is that Searle may not understand Chinese, but the system (the textbook, and its operator) do understand it. As well, with enough computational power, it may be possible for the brain to do something like this yet get a lot more mileage out of it.
Basically, the question boils down to this. Is intelligence something that can be emulated by calculation (which computers can do) or is it something more?
Is it possible for a machine to pass the Turing Test? Definitely. We have ChatGPT in 2022, but also, CAPTCHAs, which are supposed to be Turing tests for web bots, have also been broken for a long time.
Penrose used Godel’s Incompleteness Theorem to prove the impossibility of thinking machines. Since \(G(F)\) is not provable in \(F\) by any machine in \(F\), but provable by us, looking at the universe as a whole, Penrose believes that we must have some extra capability that machines do not have.
Prev: reducibility-and-gödel Next: complexity