Timothy D. Gartman

DATE @ “MMMM d, yyyy” November 7, 2018

MAT-401 Mathematical Logic – Final Paper

Douglas Frost

Alan Turing: Defining the Boundary of Human Computation

Computers are entirely ubiquitous these days. They have become so deeply ingrained in daily life that we often don’t even notice their presence. We carry them in our pockets, rely on them to assist us in driving our cars, and we even have them making our morning coffees. It is mind-boggling to think that these seemingly essential pieces of technology didn’t exist less than a century ago. Presently, computer scientists are moving ever closer to true artificial intelligence; that is, a computer that can actually think and reason of its own accord, rather than adhere rigidly to its program. Indeed, even now, we have software that can mimic human behavior to the point that other software has been developed to differentiate machine from human – specifically, CAPTCHA or “Completely Automated Public Turing test to tell Computers and Humans Apart”. The namesake of this software application is Alan Turing, whose work in mathematics, logic, and computer science served to propel us into the computing world we enjoy today.

Alan Mathison Turing was born the second son to Julius and Ethel Sara Turing in Paddington, England on June 23, 1912 CITATION Dav06 p 9 l 1033 (Leavitt 9). Turing’s interest in mathematics and science started at an early age with an interest in numbers and understanding the foundations of the relationships between these numbers. As a young boy of ten, he received a book called Natural Wonders Every Child Should Know, by Edwin Tenney Brewster. The book discussed these wonders in the context of machines. It can be argued that this connection of the natural world to machines colored Turing’s thinking and influenced his work CITATION Dav06 p 10 l 1033 (Leavitt 10). His early schooling took place at an exclusive English public school called Sherborne School where he dove heavily into science and mathematics. During his time at Sherborne, a certain literal-mindedness in Turing became apparent. He would follow instructions given to him to the letter and make no assumptions about additional meaning; that is, he behaved much in the way computers do. CITATION Dav06 p 14 l 1033 (Leavitt 14) . Following his time at Sherborne School, Turing attended and continued his studies of mathematics at King’s College in Cambridge, England. While at King’s College, Turing continued to excel in mathematics and, after graduating with honors, was awarded a fellowship for his work on proving an important result in probability theory – the central limit theorem CITATION Kop08 l 1033 (Kopieczek). It was during this fellowship that Turing began his work in logic.

The mathematical world was abounding with activity during Turing’s childhood (whether he knew it or not). During this time, David Hilbert posited the Entscheidungsproblem as an addition to his ideas on the consistency, completeness, and provability of consistency for a system of axioms (otherwise known as Hilbert’s program). The Entscheidungsproblem asserts that there is an algorithm (that is, a defined method) for determining if a given statement is provable from a set of axioms CITATION Chr16 p 9 l 1033 (Bernhardt 9). By the time Turing entered King’s College, Kurt Gödel had completed his work examining the Entscheidungsproblem and, in 1931, published the paper On Formally Undecidable Propositions of “Principia Mathematica” and Related Systems. In this seminal work, Gödel had two important results: axioms that were consistent could not be complete, and proving the consistency of axioms from within a system was impossible CITATION Chr16 p 10 l 1033 (Bernhardt 10). These results ultimately became known as Gödel’s Incompleteness Theorems and show that Hilbert’s program is impossible. Thus, when Turing learned of these results and of the Entscheidungsproblem at King’s College from Max Newman, he focused his efforts on expanding Gödel’s work and proving that Hilbert was wrong CITATION Chr16 p 11 l 1033 (Bernhardt 11).

By 1936, Turing had his answer, and it came in the form of the “Turing machine”. In his 1936 paper On Computable Numbers, with an Application to the Entscheidungsproblem, Turing took several important steps forward. First, he reframed the problems that Hilbert and Gödel were working on. Specifically, he offered a definition for the kinds of computations that mathematicians had been performing for a long time. Turing defined these computations formally as “algorithms” in terms of computing machines. These computing machines are now dubbed “Turing machines”. In essence, a Turing machine takes both a set of data and an algorithm as input and then run the data through the algorithm. Furthermore, a universal Turing machine can be used to perform any algorithm that another Turing machine could perform. The important consequence of this is that a Turing machine can be used for any algorithm CITATION Chr16 p 12 l 1033 (Bernhardt 12). With his Turing machine, he could take the next step towards disproving Hilbert.

Before describing how Turing disproved Hilbert, it is worth examining how his machine functioned. Turing’s machine involved a tape divided into squares each containing a symbol from a finite set of symbols, a movable “head” that could both read data from the tape and write to the tape, and move only one square left or right, a “state register”, and a finite table of instructions that tell the machine what to do next based on what the head is reading and what state is registered by the “state register”. These components work in concert to execute an algorithm. As symbols are read by the machine, the current state is checked, and a specific action is taken as a result. This action could be to write a 1 where a 0 was, to simply change to a different state, to write and change to a different state, etc. The end result of any Turing machine’s operation should result in a “yes” or “no”, but the operation could continue indefinitely. This last point is vital to Turing’s proof.

With this kind of computational power (which is laborious and slow, by today’s standards), Turing could claim that “everything humanly computable can also be computed by the universal Turing machine” CITATION Cop98 l 1033 (Copeland). The importance of this claim is that it establishes a boundary of what can be computed and makes it possible, therefore, to show that certain problems are not decidable. In his 1936 paper, the problem that Turing used to demonstrate undecidability is what is referred to as “the halting problem”. The halting problem seeks an algorithm that takes the algorithm for another Turing machine as its input. This algorithm should decide for any algorithm fed into it, whether the input algorithm will return a result or continue forever. Turing’s used this scenario to perform a proof by contradiction. He posited that the algorithm would only stop if the input algorithm continued running. Thus, if the one algorithm stopped, the other wouldn’tCITATION Ian17 p 247 l 1033 (Stewart 247). This was sufficient to disprove the Entscheidungsproblem.

Unbeknownst to Turing when he published his paper, another mathematician named Alonzo Church had published An Unsolvable Problem in Elementary Number Theory several weeks earlier. Church’s paper also served to disprove the Entscheidungsproblem. However, Church’s method was starkly different from his own. Church used “lambda-definable functions (functions on the positive integers whose values can be calculated by a process of repeated substitution)” CITATION Cop98 l 1033 (Copeland). Initially, Turing was concerned that his work would be unpublishable; after all, Church had published first. However, Newman (who was Turing’s mentor at the time) and he concluded that the two methods were different enough that Turing should publish. Newman even suggested that Turing should go to study with Church, who was at Princeton at the time CITATION Dav06 p 107 l 1033 (Leavitt 107). That is just what Turing did. In 1936, he travelled to the United States of America to join Alonzo Church at Princeton University to continue their work. Church spoke favorably of Turing’s On Computable Numbers, with an Application to the Entscheidungsproblem, and in 1937 Turing revised his paper to cite Church’s. Ultimately, the work of Turing and Church came to form the basis of the “Church-Turing thesis”.

Turing continued to work under Church until 1939, when he earned his PhD and published his thesis Systems of Logic Based on Ordinals. At this point, however, Turing’s work turned to somewhat more immediately practical areas. Although he was offered an opportunity to work as John von Neumann’s assistant at Princeton, Turing moved back to England in 1938 to pursue his interests in cryptography CITATION Dav06 p 139 l 1033 (Leavitt 139). Turing is now famous for his work at Bletchley Park that served to break the cryptography of the Enigma machine which provided the Allies with profound intelligence that served to turn the tide of World War II. Turing designed a machine called the “bombe” which could decrypt Enigma ciphertext by trying all 17,576 combinations of settings for the Enigma machine (which the Allies had captured by this point) in sequence until a plausible match was found CITATION Ian17 p 249 l 1033 (Stewart 249). The work he did was so effective and the Allies had so much intelligence that care had to be taken to avoid the Axis deducing that the Allies could understand their supposedly secret communication.

Following World War II, Turing moved to London and joined the private sector to work for the National Physical Laboratory. While there, he designed and worked on some of the earliest computers, including one of his own design called the ACE (Automatic Computing Engine). However, due to secrecy regarding his work at Bletchley Park, work on the ACE was slowed to the point that it was an inferior computer by the time a functional prototype was built in 1950 CITATION Chr16 p 157 l 1033 (Bernhardt 157). In that same year, Turing released a well-known paper titled Computing Machinery and Intelligence. The fundamental question this paper serves to answer is one that Turing gave in the opening paragraph – “Can machines think?”. In this paper, Turing goes on to define what he calls “The Imitation Game” which is a game played with three participants – a man, a woman, and an interrogator who is in a room separate from the other two. In this game, the interrogator must determine which of the participants is a man and which is a woman by means of asking questions. Turing used this game as the basis to argue that a machine capable of winning the imitation game could indeed think CITATION Dav06 p 242 l 1033 (Leavitt 242). Naturally, the arguments that Turing asserted in this paper were subject to much debate and objection. However, the ideas put forth have served as the basis for the field of artificial intelligence.

Not long after Turing published this paper, his life took a turn for the worse. During the investigation of a burglary of his home, it was discovered that Turing was engaged in a homosexual relationship with a man named Arnold Murray CITATION Ian17 p 253 l 1033 (Stewart 253). At that time, this was a crime of gross indecency in England and both Turing and Murray were prosecuted. In order to avoid imprisonment, Turing opted for probation and hormone therapy. His death came in 1954 as the result of cyanide poisoning. Although the coroner indicated the death was suicide, the nature of his death is still debated as there is evidence to support it was accidentalCITATION Ian17 p 254 l 1033 (Stewart 254).

Due to the esoteric nature of computers and the secrecy at Bletchley Park, the impact of Alan Turing’s work was not widely known in his short lifetime, nor were his contributions to both computer science and mathematics. However, his ideas and results have had significant effect in the shaping of the world we live in today. His efforts form the foundation of technologies that are inescapable in the modern world.

References

BIBLIOGRAPHY Bernhardt, Chris. Turing’s Vision: The Birth of Computer Science. Cambridge: The MIT Press, 2016. Book.

Copeland, B.J. Alan Turing: British mathematician and logician. 20 July 1998. Webpage. 7 11 2018. <https://www.britannica.com/biography/Alan-Turing>.

Kopieczek, Stefan. Alan Turing: ahead of his time. 1 June 2008. Webpage. 7 11 2018. <https://plus.maths.org/content/alan-turing-ahead-his-time>.

Leavitt, David. The Man Who Knew Too Much: Alan Turing and the Invention of the Computer. New York: Atlas Books, 2006. Book.

Stewart, Ian. “The Machine Stops: Alan Turing.” Stewart, Ian. Significant Figures: The Lives and Work of Great Mathematicians. New York: Joat Enterprises, 2017. 243-254. Book.