Complexity Explorer Santa Few Institute

1) Algorithms can only be run on a computer.

False - An algorithm is simply a list of step-by-step instructions. Algorithms were, in fact, originally run by hand. But they also appear in physical systems and throughout nature.

 

2) People weren't developing algorithms until the 1930s.

False - As we will see in Lecture 4-2, Boruvka's algorithm for Minimum Spanning Tree was developed in the 1920s. But Euclid's algorithm for the greatest common divisor goes back over 2000 years.

 

3) Are there functions that can be computed on an idealized, theoretical quantum computer that cannot be computed on an idealized, theoretical Turing machine?

No- Although quantum computers may be more efficient at solving certain problems, any deterministic, discrete function---in the sense specified at the beginning of the quiz---that can be computed on a quantum computer can be computed by a Turing machine, simply by having that machine simulate all of the quantum amplitudes of the quantum computer. This will be exponentially slower in general, but it is still computable.

 

4) If we make a Turing machine tape 2-dimensional, 3-dimensional, or more, does that change what can be computed?

No - It is not too difficult to simulate an n-dimensional tape by a 1-dimensional tape. You may find this a fun exercise!

 

5) If we allow a Turing machine to have infinitely many states, does that change what can be computed?

Yes - See homework problem 1.

 

6) Who first made an argument for the Church--Turing thesis?

B - Although Church, Turing, and Gödel all developed models of computation that were quickly shown to be equivalent to one another, and Church and Turing both used their models to show the existence of uncomputable problems, it was only Turing who made an argument (very convincing, in my opinion) that Turing machine accurately captured what was meant by the notion of "computable.''

 

7) The (Church--)Turing thesis is

B - The Church--Turing thesis is the assertion that any function that is "computable'' in the intuitive sense of the word is computable (in the formal sense) by a Turing machine (or any equivalent model of computation). Although there is also a "physical Church--Turing thesis''---namely, that any function computable in the physical world can be computed by a Turing machine---that is technically an extension of the original Church--Turing thesis.