Interactive classical algorithms: Preview

Abstract

This dialog paper offers a preview and provides a foretaste of an upcoming
work on the axiomatization of interactive classical algorithms.
The modern notion of algorithm was elucidated in the 1930s–1950s. It was
axiomatized a quarter of a century ago as the notion of “sequential algorithm”;
we call it “classical algorithm" here. The axiomatization was used to show that
for every classical algorithm there is a behaviorally equivalent abstract state
machine. It was also used to prove the Church-Turing thesis as it has been
understood by the logicians.
Starting from the 1960s, the notion of algorithm has expanded — probabilistic
algorithms, quantum algorithms, etc. — prompting introduction of a
much more ambitious version of the Church-Turing thesis commonly known
as the “physical thesis.” We emphasize the difference between the two versions
of the Church-Turing thesis and illustrate how nondeterministic and
probabilistic algorithms can be viewed as classical algorithms with appropriate
oracles. The same view applies to quantum circuit algorithms and many
other classes of algorithms.