# Qwiz5 Quizbowl Essentials - Turing Machine

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

*during WWII. Later he developed the*

**Enigma code***which is the basis for modern theories of*

**Turing Test***.*

**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

*. A*

**cells***reads each cell in sequence and performs a pre-determined action based on the contents of that cell.*

**head****ALONZO CHURCH**

American mathematician * Alonzo Church* was a mentor and collaborator of Alan Turing. Together they developed the

*which uses Church’s*

**Church-Turing Thesis***to prove that the Turing machine could compute any computable problem.*

__lambda calculus__*is used today in many computing languages to simplify problem solving.*

**Lambda calculus****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

*. 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.*

**Tibor Radó****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

*(oracle machines, where the machine runs automatically based on the predetermined program).*

**o-type***are sometimes called automatic machines.*

**Oracle 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!*