Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Computational capabilities of physical systems.

David H Wolpert1

  • 1NASA Ames Research Center, N269-1, Moffett Field, California 94035, USA. dhw@ptolemy.arc.nasa.gov

Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|January 22, 2002
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Estimating the amount of computation done by a brain using population neural activity.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same author

Is stochastic thermodynamics the key to understanding the energy costs of computation?

Proceedings of the National Academy of Sciences of the United States of America·2024
Same author

Entropy production in communication channels.

Physical review. E·2024
Same author

Memory Systems, the Epistemic Arrow of Time, and the Second Law.

Entropy (Basel, Switzerland)·2024
Same author

Stochastic Thermodynamics of Multiple Co-Evolving Systems-Beyond Multipartite Processes.

Entropy (Basel, Switzerland)·2023
Same author

Strengthened second law for multi-dimensional systems coupled to multiple thermodynamic reservoirs.

Philosophical transactions. Series A, Mathematical, physical, and engineering sciences·2022
Same journal

Tension on dsDNA bound to ssDNA-RecA filaments may play an important role in driving efficient and accurate homology recognition and strand exchange.

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Publisher's Note: Amplitude-phase coupling drives chimera states in globally coupled laser networks [Phys. Rev. E 91, 040901(R) (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Erratum: Shapes of sedimenting soft elastic capsules in a viscous fluid [Phys. Rev. E 92, 033003 (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Erratum: Attenuation of excitation decay rate due to collective effect [Phys. Rev. E 90, 022142 (2014)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Publisher's Note: Role of connectivity and fluctuations in the nucleation of calcium waves in cardiac cells [Phys. Rev. E 92, 052715 (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Publisher's Note: Lattice Boltzmann approach for complex nonequilibrium flows [Phys. Rev. E 92, 043308 (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
See all related articles

Physical computation has inherent accuracy limits, proving no computer can solve all universe tasks or process information faster than the universe. This establishes fundamental bounds for physical computing and information processing.

Area of Science:

  • Theoretical Computer Science
  • Foundations of Physics
  • Information Theory

Background:

  • The theoretical limits of computation are primarily understood through the lens of Turing machines (TMs).
  • The physical realizability and inherent limitations of computation within the universe remain open questions.
  • Existing models often rely on idealized systems (infinite, nonclassical, or chaotic) which may not reflect real-world constraints.

Purpose of the Study:

  • To establish strong, fundamental limits on the accuracy and capability of real-world physical computation.
  • To explore the theoretical boundaries of what any physical computer can compute, irrespective of its architecture or coupling to the universe.
  • To introduce and analyze novel computational concepts like 'prediction complexity' and their implications.

Main Methods:

Related Experiment Videos

  • Utilizing a non-Turing machine formulation of physical computation.
  • Proving the impossibility of a universal physical computer capable of solving all conceivable computational tasks.
  • Deriving analogs of the TM Halting theorem for physical computers and analyzing error-correction codes.

Main Results:

  • Proven that no physical computer can solve all computational tasks concerning the physical universe.
  • Demonstrated that no physical computer can infallibly process information faster than the universe itself.
  • Established that infallible, general-purpose observation and control apparatuses cannot exist.
  • Derived bounds on 'prediction complexity' and explored its uniqueness relative to algorithmic information complexity.

Conclusions:

  • Physical computation is fundamentally limited in accuracy and scope, irrespective of computational power or physical coupling.
  • The results imply inherent limitations on universal observation and control, with profound implications for physics and information processing.
  • The study suggests that either the universe's Hamiltonian restricts certain computations, or prediction complexity is unique, offering new perspectives on the nature of computation and the universe.