We’re Reaping Just What We Sowed

submited by

Style Pass

2025-01-09 15:00:03

Theoretical Computer Science is a glass slipper that has never quite fit the foot of practical Computer Engineering. The essence of their marriage is that theoreticians devise a formal model which captures some essential features of reality, and then apply reasoning about it to implementations. The problems occur when the models do not capture enough of the structure of real systems to explain and predict their behavior.

Some of the earliest issues in modeling computation arise in dealing with finiteness. The problem with finite computational models is that they are all equivalent in expressive power and also quite limited. This creates two issues: the inability to solve irregular problems on inputs of unbounded size (see the Pumping Lemma), and the possibility of highly specific effects that arise due to the precise numerical bound on size (as is found in finite group theory).

The idea of computing using an abstract machine model (for example, push-down automata and Turing machines) that can grow during the execution of an algorithm leads to a theory of computation that is quite rich. The implications of such models can apply to real-world computers, as long as resource utilization does not exceed their physical limitations. Even when those bounds are reached, there is still the question of what could in future be computed on machines of ever-greater size and speed. However, when even futuristic physical limitations and issues like power consumption are addressed, the correspondence between the infinitary models and reality starts to fray.