`A variant to Turing's theory of computing machines', Journal of the Association for Computing Machinery 4, 63–92

*Separate offprint of this paper. Wang made numerous research contributions to mathematical logic and the philosophy of mathematics and wrote extensively on the life and work of Kurt Goedel.*

Wang (1921-1955) was born in China but came to Harvard in 1946 to study logic & philosophy. Until 1961 he taught philosophy, first at Harvard where he'd gotten his PhD in 1948, then at Oxford, where he was the John Locke Lecturer in Philosophy in 1955. In 1961, he was appointed Gordon MacKay Professor of Mathematical Logic and Applied Mathematics at Harvard and in 1967 moved on to The Rockefeller University in New York; until about this time, most of his work was in mathematical logic & computer science

Beginning in 1967 he developed a relationship with Kurt Godel, including a series of conversations in 1971, which led to several books, including From Mathematics to Philosophy (extensively discussed with Godel and containing contributions by him) and Reflections on Kurt Godel, among others. One of his most important contributions was the invention of Wang tiles or Wang dominoes, which are squares of equal size with a different color on each edge. The problem was to find a procedure or an algorithm for figuring out if a set of these tiles will 'tile the plane' by placing them so that abutting edges are the same color. **This theoretical & mathematical problem relates to decision questions in symbolic logic, and it turns out that it also relates to Turing machines.**

* ' The principal purpose of this paper is to offer a theory which is closely related to Turing's but is more economical in the basic operations. *It will be proved that a theoretically simple basic machine can be imagined and specified such that all partial recursive functions (and hence all solvable computation problems) can be computed by it and that only four basic types of instruction are employed for the programs: shift left one space, shift right one space, mark a blank space, conditional transfer... As a result, it becomes less direct to prove that certain things can be done by the machines, but a little easier to prove that certain things cannot be done.'

(With A. W. Burks) `The logic of automata', Journal of the Association for Computing Machinery 4, 193–218, 279–297.

from Wikipedia --** 'One of the most important contributions of Wang was the invention of Wang tiles. **He showed that any Turing machine can be turned into a set of Wang tiles. The first noted example of aperiodic tiling is a set of Wang tiles, whose nonexistence Wang had once conjectured, discovered by his student Robert Berger in 1966. '.