Can a transfinite Turing machine be a good idealisation of human mathematical intuition?

WIP Seminar Series

1st session: CAN A TRANSFINITE TURING MACHINE BE A GOOD IDEALISATION OF HUMAN MATHEMATICAL INTUITION ?

Gwenaël Laurent (Cefises Center)

Abstract: An interesting question is to know whether "intuition", or more precisely, "mathematical human intuition", is a computable process or not. The issue is particularly relvant if one accepts “intuition” can be responsible for operations a computer still can't do. A very good example can be found in contextual understanding, where machines often need human monitoring. Even if it was possible for machines to have a better "intuition" in a broad range of contexts, it could be asked if this "intuition" would have anything to see with the way humans look and think about these contexts (assuming all humans share common "intuition patterns"). We can thus adress the two following questions : 

(1) Is it true that "intuition", at least in mathematics, is a unified concept, likely to be formalized under a given set of "laws" ? ;  

(2) Are these laws computable ? That is to say, would these laws be implementable by a Turing Machine ?  

In this work in progress, we suggest that "mathematical intuition" can be seen in three different prospects, as  

(a) A very propensity to seek for order (and to complete a given sequence of numbers) ;  

(b) An ability to find good first solution candidate of NP-complete problems or other intractable problems ; 

(c) The capability to see the "truth", or plausibility, of undecidable formal statements.  

It will then be shown that, if we accept these three properties, then mathematical intuition can't be described by a classical Turing Machine, but a Transfinite Turing Machine. A precise formalism of such a machine will be given, as much as the ability of this machine to solve highly "intuitive" mathematical problems. This latest step will need us to have a look at NP-complete problem structures. In this aim, a transfinite generalized version of 3-SAT will be introduced (see the more technical abstract for further details). Then it will be proven that our transfinite Turing Machine can solve this problem in a countable time. Put otherwise, P = NP would be proven to be true for our idealized concept of "mathematical intuition", although it seems less likely to be true for usual (and finite) reasoning. The consequences of these results, as well as their strong intrinsic limitations, will be discussed and open to debate. 

Technical abstract (Pdf)

To attend the seminar, please contact gwenael.laurent@uclouvain.be