# Turing machine: Quiz

Question 1: Later, Vaughan Pratt of ________ announced he had discovered a flaw in the proof (Pratt 2007).
Stanford UniversitySan Jose, CaliforniaPalo Alto, CaliforniaSilicon Valley

Question 2: In particular, ________ makes use of the Turing machine:
Complexity classNP-completeComputational complexity theoryP versus NP problem

Question 3: Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a ________ inside of a computer.
Central processing unit64-bitMicroprocessorReduced instruction set computer

Question 4: Presentation of Turing machines in context of Lambek "abacus machines" (cf ________) and recursive functions, showing their equivalence.
Register machineRandom access stored program machineCounter machineRandom access machine

Question 5: In terms of ________, a multi-tape universal Turing machine need only be slower by logarithmic factor compared to the machines it simulates.
P versus NP problemNP-completeComplexity classComputational complexity theory

Question 6: For a long time the smallest UTM was due to ________ who in 1962 discovered a 7-state 4-symbol universal Turing machine using 2-tag systems.
Chinese roomArtificial intelligenceMarvin MinskyAlan Turing

Question 7: The problem was that an answer first required a precise definition of "definite general applicable prescription", which ________ would come to call "effective calculability", and in 1928 no such definition existed.
Alfred TarskiAlan TuringKurt GödelAlonzo Church

Question 8: With regards to Hilbert's problems posed by the famous mathematician ________ in 1900, an aspect of problem #10 had been floating about for almost 30 years before it was framed precisely.
Mathematical logicKurt GödelGeorg CantorDavid Hilbert

Question 9: Like the ________ the RASP stores its "program" in "memory" external to its finite-state machine's "instructions".
Counter machineUniversal Turing machineRegister machineChurch–Turing thesis

Question 10: He cites other proposals for "universal calculating machines" included those of Percy Ludgate (1909), ________ (1914), M.
Leonardo Torres y QuevedoUnited KingdomCanadaSpain