{"id":2101,"date":"2024-10-01T00:01:29","date_gmt":"2024-10-01T04:01:29","guid":{"rendered":"https:\/\/mathvoices.ams.org\/featurecolumn\/?p=2101"},"modified":"2024-10-24T15:44:35","modified_gmt":"2024-10-24T19:44:35","slug":"people-and-computers-compared","status":"publish","type":"post","link":"https:\/\/mathvoices.ams.org\/featurecolumn\/2024\/10\/01\/people-and-computers-compared\/","title":{"rendered":"People and Computers Compared"},"content":{"rendered":"

A variety of experiments related to the Turing test have been carried out, and there are now computer programs that can systematically convince many humans that they are conversing with another human…<\/em><\/span><\/p>\n

People and Computers Compared<\/h1>\n

Joe Malkevitch
\nYork College (CUNY)<\/b><\/p>\n

Introduction<\/h2>\n

Humans—homo sapiens—often compare themselves to other
\nspecies such as dolphins, whales, elephants, chimpanzees and
\ncephalopods. Humans now know that these species exhibit intelligence and
\nin some cases display the use of tools—one of the things that humans
\ndo that we prize as being special. However, other species do not communicate with each other
\nusing written language, nor do they appear to muse over which triples of positive
\nintegers $a$, $b$ and $c$ satisfy: <\/P><\/p>\n

$$ a^2 + b^2 = c^2.$$<\/p>\n

(Such triples of integers are called Pythagorean triples<\/em>.)<\/p>\n

While there have been some claims that species other than humans
\ncan count, even if this is true to some extent they do not seem to do
\nmathematics in the sense that is necessary even to write down the
\nequation above.<\/p>\n

To assist with doing
\nmathematics, including arithmetic, humans have developed mechanical
\ndevices, calculators and computers to assist them. Many years ago, for
\nexample, the abacus was developed to speed up the process of doing calculations
\nwith numbers accurately.<\/P><\/p>\n

\"A Diagram of an abacus, courtesy of
\nWikipedia.
<\/DIV><\/p>\n

Today, we might use a supercomputer to enhance the speed with
\nwhich a mathematical calculation can be done. <\/P><\/p>\n

\"A

\nA portion of the Aurora exascale supercomputer at Argonne National Labs. Photo by Michael Linden<\/a>, CC BY-NC 2.0<\/a>.
<\/DIV><\/p>\n

The area of artificial intelligence (AI) has evolved rapidly
\nand raises questions about what humans can and cannot do that machines
\ncan also do. Here I will
\nconsider a small part of the history of mathematical interaction with machines and
\ncomputers: the theory that was developed by the mathematicians Alonzo Church and
\nAlan Turing. Church and Turing
\ninteracted as a teacher and his doctoral student, as well as in the role of fellow scholars
\nworking in the area of mathematical logic.<\/P><\/p>\n

Algorithms past and present<\/h2>\n

One fundamental issue in computer science is the
\nnotion of an algorithm. Roughly, an
\nalgorithm is a step-by-step procedure that one can carry out to accomplish a particular goal. Carrying out an algorithm is a bit like
\nfollowing a recipe for, say, baking a cake. To make a cake one assembles
\ningredients and carries out a collection of instructions, step by step.
\nNow, consider the following problem: Given the numbers 80 and 145, find $a$, the
\nlargest positive integer that divides both of these numbers, and $b$, the
\nsmallest positive integer that both of these numbers divide. One might
\nwant to design an algorithm that would solve these two specific
\ninstances of the questions of finding the greatest common divisor and
\nleast common multiple of two integers.<\/p>\n

Thinking about these
\ntwo specific problems may raise some general issues about step-by-step
\nprocedures that answer a more general or abstract question. For example,
\nperhaps you have a procedure where if there is a solution to a problem, the
\nprocedure stops after a finite amount of time with the answer. If the procedure runs for 68 hours, you might become nervous about whether
\nperhaps the procedure will never stop, or if it does stop it will do so
\nafter you are no longer alive!<\/p>\n

Though much research in modern computer science involves questions of how data and algorithms are represented in a computer, the notion of algorithm is far older. Here are general statements of two problems that we’ve already discussed in this column.<\/p>\n

Example 1:<\/strong> Fix a positive integer $N$. Find,
\nall positive integer Pythagorean triples $a$, $b$, and $c$
\nthat satisfy $a+b+c=N$. (Recall this means that
\n$a^2+b^2=c^2$.)<\/p>\n

Example 2:<\/strong>
\nGiven two positive integers $a$ and $b$, find the greatest common divisor of
\n$a$ and $b$ (the largest positive integer that divides both $a$ and $b$) and the
\nleast least common multiple of $a$ and $b$ (the smallest positive integer
\nthat both a and b divide).<\/p>\n

You may be familiar with the
\nname of Euclid of Alexandria (325 BCE—265 BCE) from having studied
\nwhat is often called Euclidean geometry in school. But perhaps you are
\nunaware that it was the same Euclid who found one method of constructing
\nPythagorean triples and developed an algorithm, now usually called the
\nEuclidean Algorithm, which finds the least common multiple of two
\npositive integers and the greatest common divisor of two positive integers. As a bonus, the Euclidean algorithm can be used to look at when the linear
\nequation $ax+by=c$, where $a$, $b$, and $c$ are positive integers, has an integer
\nsolution for the variables $x$ and $y$.
\n(In this situation $x$ and $y$ can be zero or negative.)
\nThis type of problem is now known as a diophantine equation, in honor of
\nDiaphantus (flourished 250 CE), another Greek heritage mathematician of
\nantiquity, who seems to have also lived in Alexandria in Egypt.<\/p>\n

Alonzo Church and his mathematical milieu<\/h2>\n<\/p>\n

One of the pioneers of computer science as an academic discipline was the mathematician Alonzo Church, who is usually
\nclassified as a logician within the areas that
\nmathematicians call their specialties. (The American Mathematical
\nSociety has a classification system for published research in mathematics that is updated every ten years. The current version<\/a> of this system has
\n63 broad categories, including number theory, logic, and mathematics education, and many subdivisions within these broad categories.) Church was born in Washington, D.C. Eventually
\nhe made his way to college at the University of Princeton (New Jersey) and did his
\ngraduate work in mathematics at Princeton as well.<\/p>\n

Church wrote a thesis
\nentitled Alternatives in Zermelo’s Assumptions.<\/em> This thesis
\nwas carried out under the distinguished geometer Oswald Veblen who in
\nturn had studied mathematics under the direction of E.H. Moore at the
\nUniversity of Chicago. The title of Church’s dissertation invokes the
\nname Zermelo, referring to Ernst Zermelo (1871-1953) who got his
\nadvanced degree in 1894 from the University of Berlin. <\/P><\/p>\n

\"Photo Photo of Ernst Zermelo, courtesy
\nof Wikipedia.
<\/DIV><\/p>\n

Zermelo’s name is forever associated with Zermelo-Fraenkel
\nset theory—an axiomatization of set theory that was the subject of Church’s dissertation. (Abraham Fraenkel (1891-1965) was born in Germany but
\nlater lived in Israel and became the first Dean of Mathematics at Hebrew
\nUniversity in Jerusalem.)<\/P><\/p>\n

\"Photo
\n Photo of Abraham Fraenkel, courtesy of
\nWikipedia.
<\/DIV><\/p>\n

After finishing his dissertation, Church spent two years traveling with the support of a National Research Fellowship. He returned to Princeton in 1929. Many research threads during this period
\nwere following up on ideas and problems that were developed by David
\nHilbert (1862-1942) and Kurt Gödel (1906-1978). Hilbert raised many questions about
\nsystems of axioms (rules) and what they accomplished. A fundamental property of a
\nsystem of axioms was whether or not it was consistent.<\/em> Might it be
\npossible to take a rule system and show that statement A and the
\nnegation of A both held in that system? Meanwhile, mathematics was abuzz with the work
\nthat Kurt Gödel had done in showing that in any axiomatic system
\nthat met a certain threshold of complexity,<\/em> there were statements
\nthat one could meaningfully write down where it would be impossible within the given axiom system to use the laws of logic
\nto prove that the statements were true or false. Church was stimulated to understand the
\nramifications of ideas of Hilbert and Gödel and pioneered
\ninvestigations related to various implications of this work.<\/p>\n

\"Photo
Photo of Kurt Gödel, courtesy of
\nWikipedia.
<\/DIV><\/p>\n


\"Photo
David Hilbert, photo, courtesy
\nof Wikipedia.
<\/DIV><\/p>\n

\nRemarkably, Church had
\n36 doctoral students<\/a>, nearly all of whom received their degrees from
\nPrinceton over the period from 1930 to 1988. While many researchers have
\nmany doctoral students, the set of Church’s doctoral students is
\nremarkable in terms of how famous they became as researchers themselves,
\nand sometimes—as in the case of John Kemeny (1926-1992), one of the inventors of the programming language BASIC—famous in a broader
\ncontext. Most of Church’s students would be described as logicians and
\nsome of them, like Church and his student Alan Turing, were innovators in and
\ncontributors to the emerging field of computer science. These students
\ninclude: <\/p>\n