Robert Berger (mathematician)
Encyclopedia
Robert Berger is known for inventing the first aperiodic tiling
using a set of 20,426 distinct tile shapes.
The unexpected existence of aperiodic tilings, although not Berger's explicit construction of them, follows from another result proved by Berger: that the so-called domino problem
is undecidable
. This disproves a conjecture of Hao Wang, Berger's advisor, and was published as "The Undecidability of the Domino Problem" in the Memoirs of the AMS in 1966. This paper is essentially a reprint of Berger's 1964 dissertation at Harvard University
. Berger's other two committee members were Patrick Carl Fischer and Marvin Minsky
. The result is analogous to a 1962 construction used by Kahr, Moore
, and Wang, to show that a more constrained version of the domino problem was undecidable.
Berger did his undergraduate studies at Rensselaer Polytechnic Institute
, and studied applied physics
at Harvard, earning a masters degree, before shifting to applied mathematics for his doctorate. Later, he has worked in the Digital Integrated Circuits Group of the Lincoln Laboratory
. In 2009, a paper by Berger and other Lincoln Laboratories researchers, "Wafer-scale 3D integration of InGaAs image sensors with Si readout circuits", won the best paper award at the IEEE International 3D System Integration Conference (3DIC). In 2010, a CMOS
infrared
imaging device with an analog-to-digital converter
in each pixel, coinvented by Berger, was one of R&D Magazines R&D 100 Award recipients.
Aperiodic tiling
An aperiodic tiling is a tiling obtained from an aperiodic set of tiles. Properly speaking, aperiodicity is a property of particular sets of tiles; any given finite tiling is either periodic or non-periodic...
using a set of 20,426 distinct tile shapes.
The unexpected existence of aperiodic tilings, although not Berger's explicit construction of them, follows from another result proved by Berger: that the so-called domino problem
Domino problem
In geometry, the domino problem is the problem of deciding whether a set of tiles of a particular kind admits a tiling.In a 1961 paper proposing a method for deciding an important case of David Hilbert's Entscheidungsproblem, the logician Hao Wang discussed tiling the plane by equally sized square...
is undecidable
Undecidable problem
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer....
. This disproves a conjecture of Hao Wang, Berger's advisor, and was published as "The Undecidability of the Domino Problem" in the Memoirs of the AMS in 1966. This paper is essentially a reprint of Berger's 1964 dissertation at Harvard University
Harvard University
Harvard University is a private Ivy League university located in Cambridge, Massachusetts, United States, established in 1636 by the Massachusetts legislature. Harvard is the oldest institution of higher learning in the United States and the first corporation chartered in the country...
. Berger's other two committee members were Patrick Carl Fischer and Marvin Minsky
Marvin Minsky
Marvin Lee Minsky is an American cognitive scientist in the field of artificial intelligence , co-founder of Massachusetts Institute of Technology's AI laboratory, and author of several texts on AI and philosophy.-Biography:...
. The result is analogous to a 1962 construction used by Kahr, Moore
Edward F. Moore
Edward Forrest Moore was an American professor of mathematics and computer science, the inventor of the Moore finite state machine, and an early pioneer of artificial life....
, and Wang, to show that a more constrained version of the domino problem was undecidable.
Berger did his undergraduate studies at Rensselaer Polytechnic Institute
Rensselaer Polytechnic Institute
Stephen Van Rensselaer established the Rensselaer School on November 5, 1824 with a letter to the Rev. Dr. Samuel Blatchford, in which van Rensselaer asked Blatchford to serve as the first president. Within the letter he set down several orders of business. He appointed Amos Eaton as the school's...
, and studied applied physics
Applied physics
Applied physics is a general term for physics which is intended for a particular technological or practical use.It is usually considered as a bridge or a connection between "pure" physics and engineering....
at Harvard, earning a masters degree, before shifting to applied mathematics for his doctorate. Later, he has worked in the Digital Integrated Circuits Group of the Lincoln Laboratory
Lincoln Laboratory
MIT Lincoln Laboratory, located in Lexington, Massachusetts, is a United States Department of Defense research and development center chartered to apply advanced technology to problems of national security. Research and development activities focus on long-term technology development as well as...
. In 2009, a paper by Berger and other Lincoln Laboratories researchers, "Wafer-scale 3D integration of InGaAs image sensors with Si readout circuits", won the best paper award at the IEEE International 3D System Integration Conference (3DIC). In 2010, a CMOS
CMOS
Complementary metal–oxide–semiconductor is a technology for constructing integrated circuits. CMOS technology is used in microprocessors, microcontrollers, static RAM, and other digital logic circuits...
infrared
Infrared
Infrared light is electromagnetic radiation with a wavelength longer than that of visible light, measured from the nominal edge of visible red light at 0.74 micrometres , and extending conventionally to 300 µm...
imaging device with an analog-to-digital converter
Analog-to-digital converter
An analog-to-digital converter is a device that converts a continuous quantity to a discrete time digital representation. An ADC may also provide an isolated measurement...
in each pixel, coinvented by Berger, was one of R&D Magazines R&D 100 Award recipients.