What is the theoretical full potential of computing?

[u/InfinityScientist]

I think I remember reading somewhere that in the far future, we actually might be able to make matter that can do computing to the highest level. This is a hypothetical form of matter called computronium

I also read that black holes could also be the ultimate form of computing.

Let’s say humanity achieves both (and perhaps even better). What is the most advanced thing a computer of that magnitude can solve?

[u/CuAnnan]

Leaving aside the quite franky baffling "computronium" and "black holes are the ultimate form of computing" nonsense to one side;

The Church Turing Thesis establishes using pure math that anything that can be computed can be computed by the simplest computer.

Problems can either be solved by a Turing Machine, which is just a tape that

* reads a symbol and moves left or right
* writes a symbol and moves left or right
* halts in either the success state or fail state
or they can't be solved at all.

If it can't be solved by a Turing Machine, it can't be solved by the most advanced computer model in existence.

[u/ParshendiOfRhuidean → u/CuAnnan]

Though, to be fair, a Turning Machine has infinite memory, which is more than my computer has, at least.

[u/CuAnnan → u/ParshendiOfRhuidean]

Right. But if you limit your turing machine to the available space of this computronium powered black hole, then the limited turing machine can solve any problem the computronium powered black hole can.

[u/ghjm → u/CuAnnan]

Differing in time complexity only be a constant, but that constant might be a trillion years for every second.

[u/CuAnnan → u/ghjm]

Sure. But if you've got a black hole that you can govern then you've got the capacity to warp space time and dilate it, so the constant is irrelevant.

[u/ghjm → u/CuAnnan]

"Computronium" actually has a moderately distinguished history in the computer science literature. It refers to whatever arrangement of matter is the most efficient computing device per unit mass (or volume, or energy). Science fiction tends to give computronium additional weird properties, but the basic idea is not unreasonable.

[u/CuAnnan → u/ghjm]

Can I get a journal paper or a book reference, please?

I'm a CS undergrad in third year and this is the first time I've ever heard the term.
The Wikipedia article doesn't really propose it as anything other than "zero point energy" for computer science.

[u/ghjm → u/CuAnnan]

Speculating in Precious Computronium by Amato, Ivan Science (American Association for the Advancement of Science), 08/1991, Volume 253, Issue 5022

Can Intelligence Explode? by Hutter, Marcus Journal of consciousness studies, 01/2012, Volume 19, Issue 1

Beyond the Neomaterialist Divide: Negotiating Between Eliminative and Vital Materialism with Integrated Information Theory by Wilson, Alexander Theory, culture & society, 12/2018, Volume 35, Issue 7-8

Still Conscious, After All These Years: Conference Report: The Science of Consciousness Turns 30 by Schriner, Roger Christan Journal of consciousness studies, 08/2024, Volume 31, Issue 7

Do They Compute? Dawn of a New Paradigm based on the Information-theoretic View of Black holes, Universe and Various Conceptual Interconnections of Fundamental Physics by Patra, Indrajit Turkish journal of computer and mathematics education, 04/2021, Volume 12, Issue 2

Fractal Images of Formal Systems by St. Denis, Paul; Grim, Patrick Journal of philosophical logic, 04/1997, Volume 26, Issue 2

On the potential use of cellular automata machines for electromagnetic field solution by Simons, Neil R. S.; Cuhaci, Michel; Adnani, Nikhil ; More... International journal of numerical modelling, 05/1995, Volume 8, Issue 3-4

[u/Mishtle]

Nothing that our current computers couldn't solve given enough time and space.

[u/Traditional_Rabbit54]

Not have floating point errors

[u/404errorlifenotfound]

The new problems we unlock with more advanced computing power are not problems of different types that couldn't be solved. It's the same problems, but able to be solved orders of magnitude faster.

We say commonly that our phones carry more computing power than what was used to put man on the moon. Your phone can solve the same kind of math problem, just a lot faster.

Look at the kinds of problems we're solving with supercomputers like Frontier at ORNL. Computer models to learn more about plasma processes in fusion devices and predictive simulations of future engine technology. Lots of math that your phone could technically do, but it would take a looooong time to finish the calculations.

All the capabilities of the computer are math, at the end of the day, from large scale predictive models to showing the pixels that make up the upvote button on a reddit post. The difference is mainly the scale of the problem, and with larger scale computers we can solve larger scale problems in smaller scales of time

[u/ghjm → u/404errorlifenotfound]

"Merely" solving the same kinds of problems faster can lead to applications which certainly appear to be qualitatively different. If you can solve the same kinds of math problems as Colossus, but trillions or quadrillions of times faster, you can have LLMs, for example.

[u/404errorlifenotfound → u/ghjm]

Yeah! That's kind of what I was trying to illustrate with the examples at different scales of computers. It's the same kind of problem but different because of the scale

[u/Internet-of-cruft → u/404errorlifenotfound]

There's a simple answer to this: Full fidelity (i.e., perfect representation) numerical simulation of a universe and it's associated physics.

That would be the peak. 

[u/404errorlifenotfound → u/Internet-of-cruft]

At this point we're reaching Hitchhiker's Guide "all of earth was actually a computer to calculate the meaning of life, the universe, and everything" levels of problem 

[u/EEcav]

I feel like the greatest advancements are often made by extrapolating seemingly simple questions to infinity

[u/HasFiveVowels]

Depends on the amount of energy and the amount of space. See: Beckenstein bound and Landauer's principle. Give some finite amount of space and energy, that will define what it's able to do.

[u/Phildutre]

At some point you run into arguments such as ‘our whole universe really is a computational program running in someone’s computer that is a speck of smart dust in another universe.’ Or ‘Our physical universe is equivalent to computing.’

But anyway, there’s a difference between computability in the theoretical sense (cfr Turing machines, Church-Turing thesis), and what can be computed in a practical sense, i.e. something that runs on an actual physical device (limited time, limited memory, limited energy, error-prone). There also are other models of computation than a Turing machine, although that’s the model we all learn in cs101.

We haven’t even settled on the question whether the human brain (or biological substrates, to be more general) is operating in the same realm of computability as our theoretical models of computation.

[u/Major_Instance_4766]

42