Practical Intractability: A Critique of the Hypercomputation Movement.

Aran NayebiMinds and Machines 2014 · OpenReview

TL;DR

This paper critiques the "hypercomputation movement," which proposes machines that compute beyond the limits of Turing machines but are not physically realizable. The author argues that current hypercomputation models are flawed due to reliance on infinities or physical vagueness, and proposes a shift towards extending the classical paradigm to better model real-world computational challenges like intractability and cyber-physical systems.

What Problem Does This Paper Address?

The paper addresses the ongoing debate surrounding "hypercomputation" – the idea that physical machines could compute functions that are theoretically impossible for a standard Turing machine. While proponents of hypercomputation have proposed various models, these often rely on abstract concepts like infinite time or precision, making their physical realization questionable. Critics have often focused on specific models, but the author argues for a more general, mathematically concrete challenge to the entire movement. The paper aims to demonstrate the inherent physical impossibilities in hypercomputational models and suggest a more practical direction for extending our understanding of computation.

Methods

The author's approach involves a deep dive into the foundational arguments for computability, particularly Turing's and Gandy's theses. Turing's analysis of human computation and Gandy's axiomatic principles for discrete mechanical devices are examined to establish a rigorous framework for what constitutes a physically realizable computation. The paper then introduces and applies "usability constraints" (based on Piccinini's work) to evaluate various proposed hypercomputational models. These constraints focus on aspects like readable inputs/outputs, process independence, repeatability, settability, physical constructibility, and reliability. The author uses these constraints to argue that most hypercomputational models, even those that claim to adhere to Gandy's principles, ultimately fail to be physically realizable. Finally, the paper proposes a new direction for computational theory, focusing on extending the classical paradigm to address practical limitations rather than pursuing theoretical non-computability.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Hypercomputation's Achilles' Heel: Physical Impossibility. The paper argues that the core issue with hypercomputation isn't just about specific models but a fundamental problem rooted in physical realizability, stemming from the inherent limitations of physical systems.
  • Gandy's Principles as a Robust Framework. Gandy's four principles for discrete mechanical devices are presented as a strong, generalizable framework for understanding physical computation, motivated by quantum mechanics and special relativity.
  • The "Usability Constraint" is Key. The author emphasizes that for a physical process to be considered a computation, it must be usable by a finite observer. This constraint, broken down into six sub-constraints, effectively rules out many hypercomputational models.
  • Shift Focus from Non-Computable to Intractable. The paper advocates for a move away from trying to physically compute the non-computable and towards developing computational paradigms that can better handle practically intractable problems.
  • Interactive and Cyber-Physical Systems are the Future. The author suggests that modern computing challenges, particularly in interactive systems and cyber-physical systems, are not adequately captured by the Turing machine model and represent a more fruitful area for extending computational theory.

Key Results

The paper doesn't present quantitative results in the traditional sense (e.g., accuracy scores). Instead, its key findings are theoretical and critical:

  • Demonstration of Physical Infeasibility: The author provides a mathematically concrete challenge to hypercomputability, showing that attempts to make hypercomputational models precise immediately lead to physical impossibilities, thus demonstrating their general infeasibility.
  • Critique of Existing Hypercomputation Models: Through the application of usability constraints, the paper systematically argues against the physical realizability of various proposed hypercomputational models, including partially random machines, Gandy machines producing non-computable output, and supertasks.
  • Justification for a New Direction: The paper establishes that the hypercomputation movement, in its current form, is not relevant to contemporary computer science practice and proposes a more plausible extension to the classical paradigm.

Limitations and Future Work

The author acknowledges that the "usability constraint" is preliminary and may require further refinement. While the paper focuses on discrete hypercomputation, it briefly touches upon analog hypercomputation, noting that Kieu's proposed quantum-based hypercomputer, while potentially addressing some limitations, likely still violates the usability constraint. The paper concludes by emphasizing the need for further research into extending the classical paradigm to address issues of intractability and the complexities of cyber-physical systems, suggesting this as a more practically viable and impactful direction for the future of computational theory.

Summary updated

Abstract

For over a decade, the hypercomputation movement has produced computational models that in theory solve the algorithmically unsolvable, but they are not physically realizable according to currently accepted physical theories. While opponents to the hypercomputation movement provide arguments against the physical realizability of specific models in order to demonstrate this, these arguments lack the generality to be a satisfactory justification against the construction of any information-processing machine that computes beyond the universal Turing machine. To this end, I present a more mathematically concrete challenge to hypercomputability, and will show that one is immediately led into physical impossibilities, thereby demonstrating the infeasibility of hypercomputers more generally. This gives impetus to propose and justify a more plausible starting point for an extension to the classical paradigm that is physically possible, at least in principle. Instead of attempting to rely on infinities such as idealized limits of infinite time or numerical precision, or some other physically unattainable source, one should focus on extending the classical paradigm to better encapsulate modern computational problems that are not well-expressed/modeled by the closed-system paradigm of the Turing machine. I present the first steps toward this goal by considering contemporary computational problems dealing with intractability and issues surrounding cyber-physical systems, and argue that a reasonable extension to the classical paradigm should focus on these issues in order to be practically viable.
BibTeX
@inproceedings{nayebi2014practical,
  author = {Aran Nayebi},
  title = {{Practical Intractability: A Critique of the Hypercomputation Movement.}},
  booktitle = {Minds and Machines},
  year = {2014},
  url = {https://openreview.net/forum?id=ANKT0q2sTT},
}
Figure