Jump to ContentJump to Main Navigation
The Turing Guide$
Users without a subscription are not able to see the full content.

Jack Copeland, Jonathan Bowen, Mark Sprevak, and Robin Wilson

Print publication date: 2017

Print ISBN-13: 9780198747826

Published to Oxford Scholarship Online: November 2020

DOI: 10.1093/oso/9780198747826.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (oxford.universitypressscholarship.com). (c) Copyright Oxford University Press, 2021. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in OSO for personal use. date: 18 September 2021

Turing and randomness

Turing and randomness

39 Turing and randomness
The Turing Guide

Rod Downey

Oxford University Press

In an unpublished manuscript Turing anticipated by nearly thirty years the basic ideas behind the theory of algorithmic randomness, using a computationally constrained version of ‘measure theory’ to answer a question posed by Émile Borel in number theory: this question concerned constructing what are called ‘absolutely normal’ numbers. In this chapter we explain what these mysterious terms mean, and what Turing did. Mathematicians have always been fascinated with patterns in numbers. At an early stage in our education we learn about the special nature of decimal expansions of ‘rational numbers’, fractions that we can write in the form m/n, for some whole numbers m and n with n ≠ 0. The Greeks proved that some numbers, such as √2, 3√7 and √2 + √3 are not rational—indeed, it can be shown that ‘most’ numbers (in a precise mathematical sense) are irrational. It can be shown that a real number is rational if and only if it has a finite decimal expansion, or a decimal expansion that repeats from some point onwards; for example, 1/4 = 0.25 and 3/7 = 0.428571 428571 428571... . Note that we can also think of 1/4 as a repeating decimal, 0.25000000. . . ; we can also write it as 0.24999999 ... , but for simplicity we ignore such ambiguities. We can also count using bases different from 10. The binary system uses base 2, where each place in the representation corresponds to a power of 2; for example, just as 2301 in the decimal system refers to (2 × 103) + (3 × 102) + (0 × 101) + (1 × 100), so in base 2 the decimal number 13 = (1 × 23) + (1 × 22) + (0 × 21) + (1 × 20) is represented by 1101. In base 3 we use only the numbers 0, 1, 2 and express numbers using powers of 3, so the decimal number 25 = (2 × 32) + (2 × 31) + (1 × 30) is represented by 221. Note that when we use bases larger than 10 we have to invent extra symbols to represent the larger ‘digits’; for example, in base 12 we might use the digits 0, 1, 2, . . . , 9, T, E, with T and E representing ‘ten’ and ‘eleven’.

Keywords:   algorithm design, computer science, ergodic theory, fraction, measure theory, normal number, physics, randomness

Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us .