Gödel's theorem and machines' power

Question

I was studying AI and when a question came to my mind.

I know that one of the objections to the possibility of a thinking machine examined by Turing is the so called mathematical objection, highlighting the fact that machines are subject to the same limitations showed by the Gödel theorem.

Having chosen to write an essay on this topic, mostly informal (i.e. philosophical) but precise and possibly based on a documentable underlying formal theory, I'd like to delve more into this topic. In particular, I ask mainly for references (articles or books) dealing with the following:

• a thorough explanation on why limitations of formal systems (those in the Gödel theorem's hypothesis) extend to machines;
• Turing's own view on these matters;
• how much these limitations (according to what is known today) effectively undermine the possibility of calling these machines 'intelligent' (according to the definition of 'intelligence' adopted);
• other possible links between Gödel's theorem and the possibility of designing an Artificial General Intelligence.

I have not yet decided precisely how to articulate my essay so any enlargement of the scope is welcome.

Thank to those who will contribute.

Answer 1

I'm limited by Gödel's theorem, and I'm living quite happily with that. The same would be the case with a conscious or intelligent AI. If being limited by Gödel's theorem made you not intelligent, then none of us would be intelligent.

Answer 2

You could also consider the following as broadening the scope of your essay.

Any particular algorithm for an abstract generic computer (i.e. Turing machine) can't possibly solve Halting Problem for arbitrary inputs. This obviously includes e.g. Artificial Neural Networks, as these can be encoded as a (majorly slower than on the GPU or other high-throughput deterministic devices, but still) large Turing Machine, given we can encode floating-point operations (and we can).

On the other hand, people seem to think that they can in principle give an answer for any particular instance of Halting Problem (i.e. particular problem and its input). There are open research questions which could be encoded as such problems and for which we do not have such an answer for a long time (consider Collatz conjecture, for example – the possible encoding as a Halting Problem could be, I think, an execution of exhaustive search for a proof or refutation in the selected set of basic axioms and rules of inference), but still we as a mankind still expect (I think, judging by myself) from ourselves that any of such an instances will be decided in finite time. (For Halting Problem it is impossible to decide on instance without actually running it, as far as I understand, – potentially forever.)

The combination of the former fact and the latter belief leads to the thought that the AI as we know it for now will never be able to solve the entire scope of the problems we as humans actually expect to be solvable by us.