The Turing machine is a theoretical computer designed by British mathematician Alan Turing. The machine reads cells on an infinitely large memory tape. Then, using a set of instructions pre-defined by the user, it performs an action based on the contents of the cell (Yes, it can be confusing. Watch the video below for a more visual explanation.) Essentially, the idea is that a Turing machine can determine if a particular problem can be solved by a computer. Alan Turing is considered to be the father of computer science and played a major role in breaking the Enigma code during WWII. Later he developed the Turing Test which is the basis for modern theories of artificial intelligence.
By analyzing questions, you can see patterns emerge, patterns that will help you answer questions. Qwiz5 is all about those patterns. In each installment of Qwiz5, we take an answer line and look at five of its most common clues. Here we explore five clues that will help you answer a tossup on Turing Machines.
TAPE
A fundamental component of the theoretical Turing machine is an infinitely long memory tape with an infinite number of cells. A head reads each cell in sequence and performs a pre-determined action based on the contents of that cell.
ALONZO CHURCH
American mathematician Alonzo Church was a mentor and collaborator of Alan Turing. Together they developed the Church-Turing Thesis which uses Church’s lambda calculus to prove that the Turing machine could compute any computable problem. Lambda calculus is used today in many computing languages to simplify problem solving.
HALTING PROBLEM
A limitation of the Turing machine is the so-called halting problem which states that it is impossible to determine if a problem is computable (and therefore “halts” the machine) without actually running the problem through the machine. The halting problem was further outlined by American mathematician Henry Gordon Rice in Rice’s Theorem.
BUSY BEAVER
The “busy beaver” is a special type of Turing machine that takes the maximum number of steps to solve a problem. It was theorized by Hungarian mathematician Tibor Radó. It is impossible to calculate “busy beaver” numbers for arbitrary machines since they grow faster than any computable function and calculating them would require solving the halting problem. It is possible, however, to calculate the “busy beaver” numbers for Turing machines that have a very small number of possible states.
C-TYPE and O-TYPE
Turing machines can be categorized as either c-type (choice machines, where some decisions are made by the user) or o-type (oracle machines, where the machine runs automatically based on the predetermined program). Oracle machines are sometimes called automatic machines.
***
Quizbowl is about learning, not rote memorization, so we encourage you to use this as a springboard for further reading rather than as an endpoint. Here are a few things to check out:
* Alan Turing and his work at Bletchley Park was instrumental in the Allied victory in WWII. Learn more about his time at Bletchley Park and his role in decrypting German codes here.
* Want to use a Turing machine? This website has constructed a virtual Turing machine.
* Confused by Turing machines? The website Medium published “Turing Machines for Dummies” to explain it in plain language. Read it here.
* Finally, the folks at Crash Course published this video to explain the theory behind Turing machines:
Want to learn a ton more quizbowl information, compete on thousands of questions and generally have a blast this summer? Come Qwiz with us!
Questions? Have a great idea for a future Qwiz5? We'd love to hear from you! Email us at hello@qwizbowl.com
Love this Qwiz5? Don’t forget to subscribe for updates and share this with your friends through the links below!