The Turing Guide

422 | 38 BANBURISmUS REVISITED There was already some playful language here. In 1928 the Bell Telephone Laboratories invented a ...

SImPSON | 423 chain in a particular position against the true alphabet was either wholly eliminated— indicating that some specul ...

424 | 38 BANBURISmUS REVISITED figure 38.1 Turing’s ‘comic strips’, in his handwriting. Crown copyright and reproduced with the ...

SImPSON | 425 ‘Prof ’s Book’ is a very personal document. It was evidently typed by him, with many mis-types, and the correction ...

426 | 38 BANBURISmUS REVISITED indeed the fundamental mathematical theory of the factor method. This history, which I have seen ...

CHAPTER 39 Turing and randomness rod downey I n an unpublished manuscript Turing anticipated by nearly thirty years the basic id ...

428 | 39 TURING AND RANDOmNESS 1/4 = 0.020202. . . . From now on we will drop the decimal point and concern ourselves with infin ...

DOwNEy | 429 mathe matically, we say that this ratio ‘tends to the limit 1/2’. Similarly, if we change tack and count tails inst ...

430 | 39 TURING AND RANDOmNESS we obtain the number 0.2357111317. . . . Remarkably, this number is known to be normal to base 10 ...

DOwNEy | 431 Turing’s work We recall that Turing was interested in absolute normality. Clearly, a random sequence should be abso ...

432 | 39 TURING AND RANDOmNESS Turing’s idea was first to extend the law of large numbers to ‘blocks’ of numbers. Intuitively on ...

DOwNEy | 433 We know that Turing used algorithms to generate ‘pseudo-random strings’, strings which seemed sufficiently random t ...

434 | 39 TURING AND RANDOmNESS our previous searches. But if the problem has solutions that are reasonably dense in the sample s ...

DOwNEy | 435 quickly. In a celebrated result, first announced in 2002, Manindra Agrawal, Neeraj Kayal, and Nitin Saxena gave a n ...

...

CHAPTER 40 Turing’s mentor, Max Newman ivor grattan-guinness T he interaction between mathematicians and mathematical logicians ...

438 | 40 TURING’S mENTOR, mAX NEwmAN Artur Schoenflies and Felix Hausdorff were particularly hostile to logic, targeting the fam ...

GRATTAN-GUINNESS | 439 Newman’s lecture course at Cambridge Turing’s own career provides a good example of the cleft between log ...

440 | 40 TURING’S mENTOR, mAX NEwmAN though ‘Foundations’ is now a highly respectable subject, and everybody ought to know some- ...

GRATTAN-GUINNESS | 441 member of the famous ‘Vienna Circle’, ran a preparatory seminar on ‘Algebra and logic’ while Newman was i ...