Alan M. Turing: If you build it, they will compute

 Alan M. Turing met John von Neumann in 1935, when Von Neumann was a visiting professor at Cambridge, England, and from 1936 through 1938, when Turing obtained a PhD from Princeton University.  Turing's paper on undecidability and the concept of Turing machines (particularly a universal Turing machine) influenced Von Neumann in his work on stored-program computers.  Before that, calculating machines were programmed with wiring panels or punched paper tape, which did not allow for branches in the sequence of instructions or modification of the instructions.  Turing took Von Neumann's preliminary design and completed it, which was used at Britain's National Physics Laboratory to build the Pilot ACE (Automatic Computing Engine),one of the first electronic stored-program computers.  In 1948, Turing went to The University of Manchester where he worked on the design of the Manchester Mark 1.

A Pilot ACE Simulator is available at http://www.pilotaceonline.com/index.html.

Alan M. Turing: That does not compute

In 1936, Alan M. Turing wrote a paper about computable numbers in which he described an abstract machine (which cannot be built because it would require a potentially infinite tape), that read and wrote to a tape, could move the tape left or right, and had a finite number of states which controlled its actions.  This device became known as a Turing machine.  He also described a Turing machine that could simulate any Turing machine, and used it to prove that one could not determine if a given computation would ever end.

Later, Turing and others described different models of computation, and showed that the same numbers and functions were computable under all of these models (or non-computable under all of these models).  This has brought about the assumption that all sufficiently inclusive definitions of computability are equivalent.  This is known as the Church-Turing (or Church-Turing-Tarsky) thesis.

Read more »

Alan M. Turing: Solving the mystery inside the riddle wrapped by the Enigma

During World War II, the Germans encrypted their messages using a machine called the Enigma, which used a combination of code wheels and wiring to generate a constantly changing cypher.

The Allies obtained Enigma machines and analyzed them to determine how the cypher was generated and how to break the cypher.  The British effort was housed at Bletchley Park.

Alan M. Turing had worked on the question of whether there are mathematical functions that cannot be computed; as part of this research, he described an abstract machine that could compute any function that could be described as a sequence of simple arithmetic operations.  He also had studien cryptograpy.  This led him to join Bletchley Park and work on the project to break the Enigma cypher.

Poland had obtained an Enigma machine and used it to build a preliminary version of a codebreaking machine that was called the Bomba.  Turing improved on this machine (now called the Bombe) and designed machines to crack the encryption on more complex versions of the Enigma.  He also developed some approaches that were used to manually determine the mechanism for a more sophisticated encryption machine which transmitted messages by radio.  These methods were used by Tommy Flowers in building the Colossus, one of the first large-scale special-purpose computers.

Read more »

Uniform Polyhedra and other interesting solids

Making models of polyhedra is an interesting and educational hands-on project. The resulting polyhedra have a satisfying elegance and symmetry.

 A solid is a three-dimensional geometric object; a polyhedron (plural polyhedra) is a solid made up of polygons (faces) joined at their edges.  The edges of the polygons meet at vertices (singular vertex); if faces intersect, the edges and vertices formed are called false edges and vertices. A convex polyhedron is made up of convex polygons,  has no false edges or vertices, and the interior angles between adjacent faces are all less than a straight angle (180 degrees). A compound polyhedron is one that can be separated into two or more polyhedra, with faces and edges assigned to component polyhedra without reusing or omitting any.

Read more »