William Thomas Tutte OCFRSFRSC (; 14 May 1917 – 2 May 2002) was an English and Canadian codebreaker and mathematician. During the
Second World War
World War II or the Second World War, often abbreviated as WWII or WW2, was a world war that lasted from 1939 to 1945. It involved the vast majority of the world's countries—including all of the great powers—forming two opposin ...
, he made a brilliant and fundamental advance in
cryptanalysis of the Lorenz cipher
Cryptanalysis of the Lorenz cipher was the process that enabled the British to read high-level German army messages during World War II. The British Government Code and Cypher School (GC&CS) at Bletchley Park decrypted many communications betwee ...
, a major
Nazi German
Nazi Germany (lit. "National Socialist State"), ' (lit. "Nazi State") for short; also ' (lit. "National Socialist Germany") (officially known as the German Reich from 1933 until 1943, and the Greater German Reich from 1943 to 1945) was ...
cipher system which was used for top-secret communications within the
Wehrmacht
The ''Wehrmacht'' (, ) were the unified armed forces of Nazi Germany from 1935 to 1945. It consisted of the ''Heer'' (army), the ''Kriegsmarine'' (navy) and the ''Luftwaffe'' (air force). The designation "''Wehrmacht''" replaced the previous ...
High Command. The high-level, strategic nature of the intelligence obtained from Tutte's crucial breakthrough, in the bulk decrypting of Lorenz-enciphered messages specifically, contributed greatly, and perhaps even decisively, to the defeat of Nazi Germany. He also had a number of significant mathematical accomplishments, including foundation work in the fields of
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
and
matroid theory
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...
.
Tutte's research in the field of graph theory proved to be of remarkable importance. At a time when graph theory was still a primitive subject, Tutte commenced the study of
matroid
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...
s and developed them into a theory by expanding from the work that
Hassler Whitney
Hassler Whitney (March 23, 1907 – May 10, 1989) was an American mathematician. He was one of the founders of singularity theory, and did foundational work in manifolds, embeddings, immersions, characteristic classes, and geometric integration t ...
had first developed around the mid 1930s. Even though Tutte's contributions to graph theory have been influential to modern graph theory and many of his theorems have been used to keep making advances in the field, most of his terminology was not in agreement with their conventional usage and thus his terminology is not used by graph theorists today. "Tutte advanced graph theory from a subject with one text ( D. Kőnig's) toward its present extremely active state."
Early life and education
Tutte was born in Newmarket in Suffolk. He was the younger son of William John Tutte (1873–1944), an estate gardener, and Annie (''née'' Newell; 1881–1956), a housekeeper. Both parents worked at Fitzroy House stables where Tutte was born. The family spent some time in Buckinghamshire, County Durham and Yorkshire before returning to Newmarket, where Tutte attended
Cheveley
The village of Cheveley is situated in the county of Cambridgeshire and lies about four miles east-south-east of the market town of Newmarket. The population of the civil parish was 1,990 at the 2011 Census. Cheveley falls within the local g ...
Church of England primary school in the nearby village of Cheveley. In 1927, when he was ten, Tutte won a
scholarship
A scholarship is a form of financial aid awarded to students for further education. Generally, scholarships are awarded based on a set of criteria such as academic merit, diversity and inclusion, athletic skill, and financial need.
Scholarsh ...
Trinity College, Cambridge
Trinity College is a constituent college of the University of Cambridge. Founded in 1546 by Henry VIII, King Henry VIII, Trinity is one of the largest Cambridge colleges, with the largest financial endowment of any college at either Cambridge ...
, where he specialized in
chemistry
Chemistry is the science, scientific study of the properties and behavior of matter. It is a natural science that covers the Chemical element, elements that make up matter to the chemical compound, compounds made of atoms, molecules and ions ...
and graduated with first-class honours in 1938. He continued with
physical chemistry
Physical chemistry is the study of macroscopic and microscopic phenomena in chemical systems in terms of the principles, practices, and concepts of physics such as motion, energy, force, time, thermodynamics, quantum chemistry, statistical mecha ...
as a graduate student, but transferred to mathematics at the end of 1940. As a student, he (along with three of his friends) became one of the first to solve the problem of
squaring the square
Squaring the square is the problem of tiling an integral square using only other integral squares. (An integral square is a square whose sides have integer length.) The name was coined in a humorous analogy with squaring the circle. Squaring the sq ...
, and the first to solve the problem without a squared subrectangle. Together the four created the
pseudonym
A pseudonym (; ) or alias () is a fictitious name that a person or group assumes for a particular purpose, which differs from their original or true name (orthonym). This also differs from a new name that entirely or legally replaces an individua ...
Blanche Descartes, under which Tutte published occasionally for years.
Second World War
Soon after the outbreak of the
Second World War
World War II or the Second World War, often abbreviated as WWII or WW2, was a world war that lasted from 1939 to 1945. It involved the vast majority of the world's countries—including all of the great powers—forming two opposin ...
, Tutte's tutor, Patrick Duff, suggested him for war work at the
Government Code and Cypher School
Government Communications Headquarters, commonly known as GCHQ, is an intelligence and security organisation responsible for providing signals intelligence (SIGINT) and information assurance (IA) to the government and armed forces of the Uni ...
at
Bletchley Park
Bletchley Park is an English country house and estate in Bletchley, Milton Keynes ( Buckinghamshire) that became the principal centre of Allied code-breaking during the Second World War. The mansion was constructed during the years following ...
(BP). He was interviewed and sent on a training course in London before going to Bletchley Park, where he joined the Research Section. At first, he worked on the Hagelin cipher that was being used by the Italian Navy. This was a rotor cipher machine that was available commercially, so the mechanics of enciphering was known, and decrypting messages only required working out how the machine was set up.
In the summer of 1941, Tutte was transferred to work on a project called Fish. Intelligence information had revealed that the Germans called the wireless teleprinter transmission systems ''"Sägefisch"'' (sawfish). This led the British to use the code
Fish
Fish are aquatic, craniate, gill-bearing animals that lack limbs with digits. Included in this definition are the living hagfish, lampreys, and cartilaginous and bony fish as well as various extinct related groups. Approximately 95% of li ...
for the German teleprinter cipher system. The nickname Tunny (tunafish) was used for the first non-Morse link, and it was subsequently used for the Lorenz SZ machines and the traffic that they enciphered.
Telegraphy used the 5-bitInternational Telegraphy Alphabet No. 2 (ITA2). Nothing was known about the mechanism of enciphering other than that messages were preceded by a 12-letter
indicator
Indicator may refer to:
Biology
* Environmental indicator of environmental health (pressures, conditions and responses)
* Ecological indicator of ecosystem health (ecological processes)
* Health indicator, which is used to describe the health ...
, which implied a 12-wheel rotor cipher machine. The first step, therefore, had to be to diagnose the machine by establishing the logical structure and hence the functioning of the machine. Tutte played a pivotal role in achieving this, and it was not until shortly before the Allied victory in Europe in 1945, that Bletchley Park acquired a Tunny
Lorenz cipher
The Lorenz SZ40, SZ42a and SZ42b were German rotor stream cipher machines used by the German Army during World War II. They were developed by C. Lorenz AG in Berlin. The model name ''SZ'' was derived from ''Schlüssel-Zusatz'', meaning ''cipher ...
machine. Tutte's breakthroughs led eventually to bulk decrypting of Tunny-enciphered messages between the German High Command (OKW) in Berlin and their army commands throughout occupied Europe and contributed—perhaps decisively—to the defeat of Germany.
John Tiltman
Brigadier John Hessell Tiltman, (25 May 1894 – 10 August 1982) was a British Army officer who worked in intelligence, often at or with the Government Code and Cypher School (GC&CS) starting in the 1920s. His intelligence work was largely conn ...
, Bletchley Park's veteran and remarkably gifted cryptanalyst, to deduce that it was a
Vernam cipher
Vernam is a surname. Notable people with the surname include:
*Charles Vernam (born 1996), English professional footballer
*Gilbert Vernam (1890–1960), invented an additive polyalphabetic stream cipher and later co-invented an automated one-time ...
which uses the Exclusive Or (XOR) function (symbolised by "⊕"), and to extract the two messages and hence obtain the obscuring key. After a fruitless period during which Research Section cryptanalysts tried to work out how the Tunny machine worked, this and some other keys were handed to Tutte, who was asked to "see what you can make of these".
At his training course, Tutte had been taught the
Kasiski examination
In cryptanalysis, Kasiski examination (also referred to as Kasiski's test or Kasiski's method) is a method of attacking polyalphabetic substitution ciphers, such as the Vigenère cipher. It was first published by Friedrich Kasiski in 1863, but se ...
technique of writing out a key on squared paper, starting a new row after a defined number of characters that was suspected of being the frequency of repetition of the key. If this number was correct, the columns of the matrix would show more repetitions of sequences of characters than chance alone. Tutte knew that the Tunny indicators used 25 letters (excluding J) for 11 of the positions, but only 23 letters for the other. He therefore tried Kasiski's technique on the first impulse of the key characters, using a repetition of 25 × 23 = 575. He did not observe a large number of column repetitions with this period, but he did observe the phenomenon on a diagonal. He therefore tried again with 574, which showed up repeats in the columns. Recognising that the
prime factor
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
s of this number are 2, 7 and 41, he tried again with a period of 41 and "got a rectangle of dots and crosses that was replete with repetitions".
It was clear, however, that the first impulse of the key was more complicated than that produced by a single wheel of 41 key impulses. Tutte called this component of the key (''chi''1). He figured that there was another component, which was XOR-ed with this, that did not always change with each new character, and that this was the product of a wheel that he called (''psi''1). The same applied for each of the five impulses So for a single character, the whole key K consisted of two components:
At Bletchley Park, mark impulses were signified by x and space impulses by •. For example, the letter "H" would be coded as ••x•x. Tutte's derivation of the ''chi'' and ''psi'' components was made possible by the fact that dots were more likely than not to be followed by dots, and crosses more likely than not to be followed by crosses. This was a product of a weakness in the German key setting, which they later eliminated. Once Tutte had made this breakthrough, the rest of the Research Section joined in to study the other impulses, and it was established that the five ''chi'' wheels all advanced with each new character and that the five ''psi'' wheels all moved together under the control of two ''mu'' or "motor" wheels. Over the following two months, Tutte and other members of the Research Section worked out the complete logical structure of the machine, with its set of wheels bearing cams that could either be in a position (raised) that added x to the stream of key characters, or in the alternative position that added in •.
Diagnosing the functioning of the Tunny machine in this way was a truly remarkable cryptanalytical achievement which, in the citation for Tutte's induction as an Officer of the
Order of Canada
The Order of Canada (french: Ordre du Canada; abbreviated as OC) is a Canadian state order and the second-highest honour for merit in the system of orders, decorations, and medals of Canada, after the Order of Merit.
To coincide with the ...
, was described as "one of the greatest intellectual feats of World War II".
Tutte's statistical method
To decrypt a Tunny message required knowledge not only of the logical functioning of the machine, but also the start positions of each rotor for the particular message. The search was on for a process that would manipulate the ciphertext or key to produce a frequency distribution of characters that departed from the uniformity that the enciphering process aimed to achieve. While on secondment to the Research Section in July 1942,
Alan Turing
Alan Mathison Turing (; 23 June 1912 – 7 June 1954) was an English mathematician, computer scientist, logician, cryptanalyst, philosopher, and theoretical biologist. Turing was highly influential in the development of theoretical com ...
worked out that the XOR combination of the values of successive characters in a stream of ciphertext and key emphasised any departures from a uniform distribution. The resultant stream (symbolised by the Greek letter "delta" Δ) was called the
difference
Difference, The Difference, Differences or Differently may refer to:
Music
* ''Difference'' (album), by Dreamtale, 2005
* ''Differently'' (album), by Cassie Davis, 2009
** "Differently" (song), by Cassie Davis, 2009
* ''The Difference'' (al ...
because XOR is the same as modulo 2 subtraction.
The reason that this provided a way into Tunny was that although the frequency distribution of characters in the ciphertext could not be distinguished from a random stream, the same was not true for a version of the ciphertext from which the ''chi'' element of the key had been removed. This was the case because where the plaintext contained a repeated character and the ''psi'' wheels did not move on, the differenced ''psi'' character () would be the null character ('/ ' at Bletchley Park). When XOR-ed with any character, this character has no effect. Repeated characters in the plaintext were more frequent both because of the characteristics of German (EE, TT, LL and SS are relatively common), and because telegraphists frequently repeated the figures-shift and letters-shift characters as their loss in an ordinary telegraph message could lead to gibberish.
To quote the General Report on Tunny:
Turingery introduced the principle that the key differenced at one, now called ΔΚ, could yield information unobtainable from ordinary key. This Δ principle was to be the fundamental basis of nearly all statistical methods of wheel-breaking and setting.
Tutte exploited this amplification of non-uniformity in the differenced values and by November 1942 had produced a way of discovering wheel starting points of the Tunny machine which became known as the "Statistical Method". The essence of this method was to find the initial settings of the ''chi'' component of the key by exhaustively trying all positions of its combination with the ciphertext, and looking for evidence of the non-uniformity that reflected the characteristics of the original plaintext. Because any repeated characters in the plaintext would always generate •, and similarly would generate • whenever the ''psi'' wheels did not move on, and about half of the time when they did – some 70% overall.
As well as applying differencing to the full 5-bit characters of the ITA2 code, Tutte applied it to the individual impulses (bits). The current ''chi'' wheel cam settings needed to have been established to allow the relevant sequence of characters of the ''chi'' wheels to be generated. It was totally impracticable to generate the 22 million characters from all five of the ''chi'' wheels, so it was initially limited to 41 × 31 = 1271 from the first two. After explaining his findings to
Max Newman
Maxwell Herman Alexander Newman, FRS, (7 February 1897 – 22 February 1984), generally known as Max Newman, was a British mathematician and codebreaker. His work in World War II led to the construction of Colossus, the world's first operatio ...
, Newman was given the job of developing an automated approach to comparing ciphertext and key to look for departures from randomness. The first machine was dubbed
Heath Robinson
William Heath Robinson (31 May 1872 – 13 September 1944) was an English cartoonist, illustrator and artist, best known for drawings of whimsically elaborate machines to achieve simple objectives.
In the UK, the term "Heath Robinson cont ...
, but the much faster
Colossus computer
Colossus was a set of computers developed by British codebreakers in the years 1943–1945 to help in the cryptanalysis of the Lorenz cipher. Colossus used thermionic valves (vacuum tubes) to perform Boolean and counting operations. Colossus ...
, developed by
Tommy Flowers
Thomas Harold Flowers MBE (22 December 1905 – 28 October 1998) was an English engineer with the British General Post Office. During World War II, Flowers designed and built Colossus, the world's first programmable electronic computer, to help ...
and using algorithms written by Tutte and his colleagues, soon took over for breaking codes.
Doctorate and career
In late 1945, Tutte resumed his studies at
Cambridge
Cambridge ( ) is a university city and the county town in Cambridgeshire, England. It is located on the River Cam approximately north of London. As of the 2021 United Kingdom census, the population of Cambridge was 145,700. Cambridge bec ...
, now as a graduate student in mathematics. He published some work begun earlier, one a now famous paper that characterises which graphs have a perfect matching, and another that constructs a non-Hamiltonian graph.
Tutte completed a doctorate in mathematics from Cambridge in 1948 under the supervision of
Shaun Wylie
Shaun Wylie (17 January 1913 – 2 October 2009
The same year, invited by
Harold Scott MacDonald Coxeter
Harold Scott MacDonald "Donald" Coxeter, (9 February 1907 – 31 March 2003) was a British and later also Canadian geometer. He is regarded as one of the greatest geometers of the 20th century.
Biography
Coxeter was born in Kensington t ...
, he accepted a position at the
University of Toronto
The University of Toronto (UToronto or U of T) is a public research university in Toronto, Ontario, Canada, located on the grounds that surround Queen's Park. It was founded by royal charter in 1827 as King's College, the first institution ...
. In 1962, he moved to the
University of Waterloo
The University of Waterloo (UWaterloo, UW, or Waterloo) is a public research university with a main campus in Waterloo, Ontario
Waterloo is a city in the Canadian province of Ontario. It is one of three cities in the Regional Municipality ...
in Waterloo, Ontario, where he stayed for the rest of his academic career. He officially retired in 1985, but remained active as an emeritus professor. Tutte was instrumental in helping to found the Department of Combinatorics and Optimization at the University of Waterloo.
His mathematical career concentrated on
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...
, especially
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, which he is credited as having helped create in its modern form, and
matroid theory
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...
, to which he made profound contributions; one colleague described him as "the leading mathematician in combinatorics for three decades". He was editor in chief of the ''
Journal of Combinatorial Theory
The ''Journal of Combinatorial Theory'', Series A and Series B, are mathematical journals specializing in combinatorics and related areas. They are published by Elsevier. ''Series A'' is concerned primarily with structures, designs, and applicat ...
'' until retiring from Waterloo in 1985. He also served on the editorial boards of several other mathematical research journals.
Research contributions
Tutte's work in
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
includes the structure of
cycle space
In graph theory, a branch of mathematics, the (binary) cycle space of an undirected graph is the set of its even-degree subgraphs.
This set of subgraphs can be described algebraically as a vector space over the two-element finite field. The dime ...
s and
cut space
In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. Any cut determines a cut-set, the set of edges that have one endpoint in each subset of the partition. These edges are said to cross the cut. In a connect ...
s, the size of
maximum matching
Maximum cardinality matching is a fundamental problem in graph theory.
We are given a graph , and the goal is to find a matching containing as many edges as possible; that is, a maximum cardinality subset of the edges such that each vertex is adj ...
Hamiltonian
Hamiltonian may refer to:
* Hamiltonian mechanics, a function that represents the total energy of a system
* Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system
** Dyall Hamiltonian, a modified Hamiltonian ...
and non-Hamiltonian graphs. He disproved
Tait's conjecture
In mathematics, Tait's conjecture states that "Every 3-connected planar cubic graph has a Hamiltonian cycle (along the edges) through all its vertices". It was proposed by and disproved by , who constructed a counterexample with 25 faces, 69 e ...
, on the Hamiltonicity of
polyhedral graph
In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-con ...
s, by using the construction known as
Tutte's fragment
In mathematics, Tait's conjecture states that "Every 3-connected planar cubic graph has a Hamiltonian cycle (along the edges) through all its vertices". It was proposed by and disproved by , who constructed a counterexample with 25 faces, 69 e ...
. The eventual proof of the
four colour theorem
In mathematics, the four color theorem, or the four color map theorem, states that no more than four colors are required to color the regions of any map so that no two adjacent regions have the same color. ''Adjacent'' means that two regions sha ...
made use of his earlier work. The graph polynomial he called the "dichromate" has become famous and influential under the name of the
Tutte polynomial
The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph G and contai ...
and serves as the prototype of combinatorial invariants that are universal for all invariants that satisfy a specified reduction law.
The first major advances in
matroid theory
In combinatorics, a branch of mathematics, a matroid is a structure that abstracts and generalizes the notion of linear independence in vector spaces. There are many equivalent ways to define a matroid axiomatically, the most significant being ...
were made by Tutte in his 1948 Cambridge PhD thesis which formed the basis of an important sequence of papers published over the next two decades. Tutte's work in graph theory and matroid theory has been profoundly influential on the development of both the content and direction of these two fields. In matroid theory, he discovered the highly sophisticated homotopy theorem and founded the studies of chain groups and
regular matroid
In mathematics, a regular matroid is a matroid that can be represented over all fields.
Definition
A matroid is defined to be a family of subsets of a finite set, satisfying certain axioms. The sets in the family are called "independent sets". On ...
s, about which he proved deep results.
In addition, Tutte developed an algorithm for determining whether a given
binary matroid
In matroid theory, a binary matroid is a matroid that can be represented over the finite field GF(2).. That is, up to isomorphism, they are the matroids whose elements are the columns of a (0,1)-matrix and whose sets of elements are independent i ...
is a
graphic matroid
In the mathematical theory of matroids, a graphic matroid (also called a cycle matroid or polygon matroid) is a matroid whose independent sets are the forests in a given finite undirected graph. The dual matroids of graphic matroids are called co- ...
. The algorithm makes use of the fact that a planar graph is simply a graph whose circuit-matroid, the dual of its bond-matroid, is graphic.
Tutte wrote a paper entitled ''How to Draw a Graph'' in which he proved that any face in a 3-connected graph is enclosed by a
peripheral cycle
In graph theory, a peripheral cycle (or peripheral circuit) in an undirected graph is, intuitively, a cycle that does not separate any part of the graph from any other part. Peripheral cycles (or, as they were initially called, peripheral polygo ...
. Using this fact, Tutte developed an alternative proof to show that every Kuratowski graph is non-planar by showing that ''K''5 and ''K''3,3 each have three distinct peripheral cycles with a common edge. In addition to using peripheral cycles to prove that the Kuratowski graphs are non-planar, Tutte proved that every simple 3-connected graph can be drawn with all its faces convex, and devised an algorithm which constructs the plane drawing by solving a linear system. The resulting drawing is known as the Tutte embedding.
Tutte's algorithm makes use of the barycentric mappings of the peripheral circuits of a simple 3-connected graph.
The findings published in this paper have proved to be of much significance because the algorithms that Tutte developed have become popular planar graph drawing methods.
One of the reasons for which Tutte's embedding is popular is that the necessary computations that are carried out by his algorithms are simple and guarantee a one-to-one correspondence of a graph and its embedding onto the
Euclidean plane
In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions of ...
, which is of importance when parameterising a three-dimensional mesh to the plane in geometric modelling. "Tutte's theorem is the basis for solutions to other computer graphics problems, such as
morphing
Morphing is a special effect in motion pictures and animations that changes (or morphs) one image or shape into another through a seamless transition. Traditionally such a depiction would be achieved through dissolving techniques on film. Since ...
."
Tutte was mainly responsible for developing the theory of
enumeration
An enumeration is a complete, ordered listing of all the items in a collection. The term is commonly used in mathematics and computer science to refer to a listing of all of the elements of a set. The precise requirements for an enumeration (fo ...
of planar graphs, which has close links with chromatic and dichromatic polynomials. This work involved some highly innovative techniques of his own invention, requiring considerable manipulative dexterity in handling power series (whose coefficients count appropriate kinds of graphs) and the functions arising as their sums, as well as geometrical dexterity in extracting these power series from the graph-theoretic situation.
Tutte summarised his work in the ''Selected Papers of W.T. Tutte'', 1979, and in ''Graph Theory as I have known it'', 1998.
Positions, honours and awards
Tutte's work in World War II and subsequently in combinatorics brought him various positions, honours and awards:
* 1958, Fellow of the
Royal Society of Canada
The Royal Society of Canada (RSC; french: Société royale du Canada, SRC), also known as the Academies of Arts, Humanities and Sciences of Canada (French: ''Académies des arts, des lettres et des sciences du Canada''), is the senior national, bil ...
(FRSC);
* 1971,
Jeffery–Williams Prize The Jeffery–Williams Prize is a mathematics award presented annually by the Canadian Mathematical Society. The award is presented to individuals in recognition of outstanding contributions to mathematical research. The first award was presen ...
Henry Marshall Tory Medal
The Henry Marshall Tory Medal is an award of the Royal Society of Canada "for outstanding research in a branch of astronomy, chemistry, mathematics, physics, or an allied science". It is named in honour of Henry Marshall Tory and is awarded bi-ann ...
by the Royal Society of Canada;
* 1977, A conference on Graph Theory and Related Topics was held at the
University of Waterloo
The University of Waterloo (UWaterloo, UW, or Waterloo) is a public research university with a main campus in Waterloo, Ontario
Waterloo is a city in the Canadian province of Ontario. It is one of three cities in the Regional Municipality ...
in his honour on the occasion of his sixtieth birthday;
* 1982,
Isaak-Walton-Killam Award
The Izaak Walton Killam Memorial Prize was established according to the will of Dorothy J. Killam to honour the memory of her husband Izaak Walton Killam.
Five Killam Prizes, each having a value of $100,000, are annually awarded by the Canada Cou ...
by the
Canada Council
The Canada Council for the Arts (french: Conseil des arts du Canada), commonly called the Canada Council, is a Crown corporation established in 1957 as an arts council of the Government of Canada. It acts as the federal government's principal i ...
;
* 1987,
Fellow of the Royal Society
Fellowship of the Royal Society (FRS, ForMemRS and HonFRS) is an award granted by the judges of the Royal Society of London to individuals who have made a "substantial contribution to the improvement of natural science, natural knowledge, incl ...
(FRS);
* 1990–1996, First President of the
Institute of Combinatorics and its Applications
The Institute of Combinatorics and its Applications (ICA) is an international scientific organization formed in 1990 to increase the visibility and influence of the combinatorial community. In pursuit of this goal, the ICA sponsors conferences, ...
;
* 1998, Appointed honorary director of the
Centre for Applied Cryptographic Research
The Centre for Applied Cryptographic Research (CACR) is a group of industrial representatives, professors, and students at the University of Waterloo in Waterloo, Ontario, Canada who work and do research in the field of cryptography.
The CACR aim ...
at the University of Waterloo;
* 2001, Officer of the
Order of Canada
The Order of Canada (french: Ordre du Canada; abbreviated as OC) is a Canadian state order and the second-highest honour for merit in the system of orders, decorations, and medals of Canada, after the Order of Merit.
To coincide with the ...
(OC);
* 2001,
CRM-Fields-PIMS prize
The CRM-Fields-PIMS Prize is the premier Canadian research prize in the mathematical sciences. It is awarded in recognition of exceptional research achievement in the mathematical sciences and is given annually by three Canadian mathematics institu ...
.
* 2016, Waterloo Region Hall of Fame
* 2017, Waterloo "William Tutte Way" road naming
Tutte served as Librarian for the
Royal Astronomical Society of Canada
Royal may refer to:
People
* Royal (name), a list of people with either the surname or given name
* A member of a royal family
Places United States
* Royal, Arkansas, an unincorporated community
* Royal, Illinois, a village
* Royal, Iowa, ...
in 1959–1960, and asteroid 14989 Tutte (1997 UB7) was named after him.
Because of Tutte's work at Bletchley Park, Canada's
Communications Security Establishment
The Communications Security Establishment (CSE; french: Centre de la sécurité des télécommunications, ''CST''), formerly (from 2008-2014) called the Communications Security Establishment Canada (CSEC), is the Government of Canada's national ...
named an internal organisation aimed at promoting research into cryptology, the Tutte Institute for Mathematics and Computing (TIMC), in his honour in 2011.
In September 2014, Tutte was celebrated in his hometown of Newmarket, England, with the unveiling of a sculpture, after a local newspaper started a campaign to honour his memory.
Bletchley Park in Milton Keynes celebrated Tutte's work with an exhibition ''Bill Tutte: Mathematician + Codebreaker'' from May 2017 to 2019, preceded on 14 May 2017 by lectures about his life and work during the Bill Tutte Centenary Symposium.
Personal life and death
In addition to the career benefits of working at the new
University of Waterloo
The University of Waterloo (UWaterloo, UW, or Waterloo) is a public research university with a main campus in Waterloo, Ontario
Waterloo is a city in the Canadian province of Ontario. It is one of three cities in the Regional Municipality ...
, the more rural setting of
Waterloo County
Waterloo County was a county in the Canadian province of Ontario from 1853 until 1973. It was the direct predecessor of the Regional Municipality of Waterloo.
Situated on a subset of land within the Haldimand Tract, the traditional territory of ...
appealed to Bill and his wife Dorothea. They bought a house in the nearby village of
West Montrose, Ontario
West Montrose is an unincorporated rural community in Woolwich Township in the Regional Municipality of Waterloo, Ontario, Canada. As of the 2016 census, the population of the community
was 257.
The settlement of West Montrose is designated a ...
where they enjoyed hiking, spending time in their garden on the Grand River and allowing others to enjoy the beautiful scenery of their property.
They also had an extensive knowledge of all the birds in their garden. Dorothea, an avid potter, was also a keen hiker and Bill organised hiking trips. Even near the end of his life Bill still was an avid walker. After his wife died in 1994, he moved back to Newmarket (Suffolk), but then returned to Waterloo in 2000, where he died two years later. He is buried in West Montrose United Cemetery.
Select publications
Books
*
*. Also
*
*
** Volume I:
** Volume II:
* Reprinted by Cambridge University Press 2001,
* Reprinted 2012,
Articles
*
See also
*
List of University of Waterloo people
The University of Waterloo, located in Waterloo, Ontario, Canada, is a comprehensive public university that was founded in 1957 by Drs. Gerry Hagey and Ira G. Needles. It has grown into an institution of more than 42,000 students, faculty, and ...
* Appendix 5 in
*
*
* in
* Updated and extended version of ''Action This Day: From Breaking of the Enigma Code to the Birth of the Modern Computer'' Bantam Press 2001
* That version is a facsimile copy, but there is a transcript of much of this document in '.pdf' format at: , and a web transcript of Part 1 at:
* in
*
*
* Transcript of a lecture given by Prof. Tutte at the
University of Waterloo
The University of Waterloo (UWaterloo, UW, or Waterloo) is a public research university with a main campus in Waterloo, Ontario
Waterloo is a city in the Canadian province of Ontario. It is one of three cities in the Regional Municipality ...
The New York Times
''The New York Times'' (''the Times'', ''NYT'', or the Gray Lady) is a daily newspaper based in New York City with a worldwide readership reported in 2020 to comprise a declining 840,000 paid print subscribers, and a growing 6 million paid ...
The Guardian
''The Guardian'' is a British daily newspaper. It was founded in 1821 as ''The Manchester Guardian'', and changed its name in 1959. Along with its sister papers ''The Observer'' and ''The Guardian Weekly'', ''The Guardian'' is part of the Gu ...
The Daily Telegraph
''The Daily Telegraph'', known online and elsewhere as ''The Telegraph'', is a national British daily broadsheet newspaper published in London by Telegraph Media Group and distributed across the United Kingdom and internationally.
It was fo ...