Computation as a universal and fundamental concept

Post by masfuerte » Sat, Jul 11, 2026, 11:56 AM UTC

justinpombrio wrote: post #66

joelshep wrote: post #30

Earlier quoted context omitted.

I may be misremembering Godel's proof or misunderstanding your last paragraph, but I thought Godel's proof actually presented a specific undecidable statement. The hope then was that somehow undecidable statements could be cordoned off from decidable statements, and Turing's result showed that that wasn't possible. Perhaps that's what you mean by "the nonexistence of a single algorithm that correctly answers every in…

There's no such thing as an undecidable statement. A single statement can't be undecidable. Undecidability is a property of a class of statements. For example, you can ask whether a Java program, run with infinite memory, will eventually halt. For any particular Java program, there's obviously an algorithm that says whether it halts or not. The algorithm is a single statement, which says either "yes" or "no". Might b…

Post by aeonik » Sat, Jul 11, 2026, 12:48 PM UTC

voidhorse wrote: post #97

BirAdam wrote: post #73

Earlier quoted context omitted.

I’ve always hated the use of the word “information” in relation to things like spin. Information and order are effects of human perception and preference. They exist as abstractions in the mind and not in reality.

This. I'll never understand people who reify "information" as though it is some object with independent existence from man. No information without an interpretation. The "amount" of information is completely dependent on the observer. You'd think people who work constantly with abstraction wouldn't fall prey to reifying abstractions but they actually seem more susceptible to it than anyone else.

Post by peter_m1 » Sat, Jul 11, 2026, 12:57 PM UTC

wasabi991011 wrote: post #76

Maxatar wrote: post #5

Earlier quoted context omitted.

>Recently it's been shown that there are real, physical processes which are undecidable I want to push back a bit on this claim along two dimensions. Imagine a physical Turing machine built out of atoms, gears, levers, and an electron parked on the read/write head and ask whether that electron ever crosses some fixed plane in space, which it does only when the machine enters its halt configuration. That's now a purel…

Agreed, and I'll add: the universe is sufficiently messy and complex that some of the claimed undecidability results may never occur in practice. For your Turing machine example: even if we built such a machine, it would never truly be giving an answer to the halting problem, because any stray cosmic particle could excite the electron and cause it to cross whatever plane. For a more realistic example: the ground stat…

Post by peter_m1 » Sat, Jul 11, 2026, 1:02 PM UTC

jesuslop wrote: post #68

Maxatar wrote: post #5

Earlier quoted context omitted.

>Recently it's been shown that there are real, physical processes which are undecidable I want to push back a bit on this claim along two dimensions. Imagine a physical Turing machine built out of atoms, gears, levers, and an electron parked on the read/write head and ask whether that electron ever crosses some fixed plane in space, which it does only when the machine enters its halt configuration. That's now a purel…

I think Gödel undecidable sentence is always relative to a formal system (the title of the paper spoke about systems in the expressive power rank of Russell's Principia, of which he gives one particular example assuming it shows how his methods apply to the whole family of systems), but now Hilbert problem #6 still stands for the lack of a comprehensive axiomatization of Physics, as its modern heir the mass-gap mille…

Post by peter_m1 » Sat, Jul 11, 2026, 1:14 PM UTC

woopsn wrote: post #44

gradys wrote: post #4

Earlier quoted context omitted.

It can be the case that both: - The physics of the universe can be completely modeled as computation, and - It's possible to pose undecidable problems about the way the universe unfolds This is intrinsic to the idea of undecidability even for Turing machines, e.g. "we equate computation with the functioning of Turing machines, but there are real processes executable in Turing machines that are undecidable".

A key thing about the undecidability problem wrt physics is preparation of the initial state. In math and computer science it is relatively straightforward to prepare such problems now (though this represented an enormous leap conceptually), but the "undecidability" of all physical problems relies on construction of materials that are clearly unconstructable - systems of infinite negentropy (eg Turing machines), infi…