Talk:Randomness
From Maze
(Difference between revisions)
(Moving Jeremy's discussion of Turing) | |||
| Line 1: | Line 1: | ||
| − | review by Noah 7/12/2011 | + | == Turing and Randomness == |
| + | |||
| + | Since the 1950s, most computer systems have offered a function to generate random numbers. One of the earliest examples is the world’s first commercial general-purpose computer, the Ferranti Mark I, whose /W function was used by Christopher Strachey in his 1952 love letter generator program. The instruction was added directly due to the work of Alan Turing, and in the 1951 documentation, Turing wrote that: | ||
| + | |||
| + | <blockquote>"[T]he principle that the state of the machine at one completion signal determines the state at the next is abandoned if instructions with function symbol /W are used. The behaviour of the machine is then to be described as a ‘stochastic’ (i.e. chance-controlled) process and is suitable for calculations concerned with stochastic processes. The instruction /W actually puts random digits into the twenty least significant digits of the accumulator."</blockquote> | ||
| + | |||
| + | [*NOTE*: The following paragraph may be too technical, and may also need to cut this down if it is too much of an aside. Need to fact-check the assertion that *for Turing* adding the /W instruction was related to Mersenne research, perhaps in: Lavington, Simon (1998), A History of Manchester Computers (2 ed.), Swindon: The British Computer Society. See also Brian Napper, The Mathematics Department and the Mark 1. http://www.computer50.org/mark1/maths.html] | ||
| + | |||
| + | Turing's addition of a built-in random function (not present in the Manchester prototype) may have grown out of his research interests in the search for large prime numbers, in particular his early work with Newman on using the early Manchester machines to search for Mersenne primes (i.e. primes amounting to one less than a power of two). Turing's 1949 prime search was implemented following the approach of Derrick Lehmer, who had developed the Lucas–Lehmer primality test. Turing's computational application of Lehmer's approach was later successfully applied by Lehmer's colleague Raphael Mitchel Robinson in 1952 in discovering the next five Mersenne primes (521, 607, 1279, 2203, 2281), and indeed has been used in all 30 discoveries of Mersenne primes since then, and is still used today in the distributed computing efforts of the Great Internet Prime Search. Lehmer, in turn, proposed in 1949 the linear congruential model for random number generation, a model which depended on relative primes in general and Mersenne primes in particular to generate long sequences of pseudorandom numbers. Both linear congruential generators (LCGs) in general and Lehmer random number generators (LRNGs) specifically would later be used in a variety of programming languages and computing platforms, including Dartmouth BASIC, the ZX Spectrum, and (in heavily modified form) in the 6502 Microsoft BASIC that became the core of Commodore BASIC in the Commodore PET, VIC-20, and 64. | ||
| + | |||
| + | <blockquote> | ||
| + | Lehmer, D. H. (1949). "Mathematical methods in large-scale computing units". Proceedings of a Second Symposium on Large-Scale Digital Calculating Machinery: 141–146. MR0044899. (journal version: Annals of the Computation Laboratory of Harvard University, Vol. 26 (1951)). | ||
| + | http://www.reginaldtiangha.com/cpsc509/ferranti.htm | ||
| + | http://www.alpha60.de/research/muc/ | ||
| + | http://www.alpha60.de/research/muc/Link_MustBeAnAngel_2006.pdf | ||
| + | </blockquote> | ||
| + | |||
| + | == review by Noah 7/12/2011 == | ||
-add Cage transcendental thought, transcendental/random numbers | -add Cage transcendental thought, transcendental/random numbers | ||
