Abstract

We characterize computer science as an interplay between two modes of reasoning: the Aristotelian (procedural) method and the Platonic (declarative) approach. We contend that Aristotelian, step-by-step thinking dominates in computer programming, while Platonic, static reasoning plays a more prominent role in computational complexity. Various frameworks elegantly blend both Aristotelian and Platonic reasoning. A key example explored in this paper concerns nondeterministic polynomial time Turing machines. Beyond this interplay, we emphasize the growing importance of the ‘computing by observing’ paradigm, which posits that a single derivation tree—generated with a string-rewriting system—can yield multiple interpretations depending on the choice of the observer. Advocates of this paradigm formalize the Aristotelian activities of rewriting and observing within automata theory through a Platonic lens. This approach raises a fundamental question: How do these Aristotelian activities re-emerge when the paradigm is formulated in propositional logic? By addressing this issue, we develop a novel simulation method for nondeterministic Turing machines, particularly those bounded by polynomial time, improving upon the standard textbook approach.