×

How not to use the Church-Turing thesis against Platonism. (English) Zbl 1266.00018

The author replies to an argument by Olzewski, who claimed that the Church-Turing thesis is incompatible with mathematical platonism. Oleszewski’s argument rest on the claim that by platonism there exists a function which some machine involving a random device computes, although the function is not effectively computable. The author refutes this argument conclusively. Firstly, Olszewski’s argument, if correct, might really be understood as undermining the Church-Turing thesis, and not platonism. More importantly, however, the function used in the argument is not effectively computable as it involves an unspecified way of finding the next number of random sequence. The author outlines the involved concepts of random functions and computatibility in detail.

MSC:

00A30 Philosophy of mathematics
03A05 Philosophical and critical aspects of logic and foundations
03D10 Turing machines and related notions
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
Full Text: DOI