Hacker NewsTypechecking is undecideable when 'type' is a type (1989) [pdf]
https://dspace.mit.edu/bitstream/handle/1721.1/149366/MIT-LCS-TR-458.pdf
#HackerNews #Typechecking #undecidability #type #theory #1989 #MIT #research #pdf
Chuck DarwinUndecidability is a feature of physical theories and cannot literally exist in real experiments.
Only idealized systems that involve infinity
—an infinitely long tape, an infinitely extensive grid of particles, an infinitely divisible space for placing pinballs and rubber ducks
—can be truly undecidable.
No one knows whether reality contains these sorts of infinities,
but experiments definitely don’t.
Every object on a lab bench has a finite number of molecules, and every measured location has a final decimal place.
We can, in principle, completely understand these finite systems by systematically listing every possible configuration of their parts.
So because humans can’t interact with the infinite, some researchers consider undecidability to be of limited practical significance.
Other physicists, however, emphasize that infinite theories are a close
—and essential
—approximation of the real world.
Climate scientists and meteorologists run computer simulations that treat the ocean as if it were a continuous fluid,
because no one can analyze the ocean molecule by molecule.
They need the infinite to help make sense of the finite.
In that sense, some researchers consider infinity
—and undecidability
—to be an unavoidable aspect of our reality.
“It’s sort of solipsistic to say: ‘There are no infinite problems because ultimately life is finite,’” Moore said.
And so physicists must accept a new obstacle in their quest to acquire the foresight of Laplace’s demon.
They could conceivably work out all the laws that describe the universe, just as they have worked out all the laws that describe pinball machines, quantum materials, and the trajectories of rubber ducks.
But they’re learning that those laws aren’t guaranteed to provide shortcuts that allow theorists to fast-forward a system’s behavior and foresee all aspects of its fate.
The universe knows what to do and will continue to evolve with time,
but its behavior appears to be rich enough that certain aspects of its future may remain forever hidden to the theorists who ponder it.
They will have to be satisfied with being able to discover where those impenetrable pockets lie.
“You’re trying to discover something about the way the universe or mathematics works,” Cubitt said.
“The fact that it’s unsolvable, and you can prove that, is an answer.”
#undecidability
Reality has repeatedly humbled Physicist's ambitions to predict future states of systems
One blow came in the early 1900s with the discovery of quantum mechanics. Whenever quantum particles are not being measured, they inhabit a fundamentally fuzzy realm of possibilities. They don’t have a precise position for a demon to know.
Another came later that century, when physicists realized how much “chaotic” systems amplified any uncertainties. A demon might be able to predict the weather in 50 years, but only with an infinite knowledge of the present all the way down to every beat of every butterfly’s wing.
In recent years, a third limitation has been percolating through physics—in some ways the most dramatic yet. Physicists have found it in collections of quantum particles, along with classical systems like swirling ocean currents. Known as #undecidability, it goes beyond chaos.
Even a demon with perfect knowledge of a system’s state would be unable to fully grasp its future.
“I give you God’s view,” said Toby Cubitt, a physicist turned computer scientist at University College London and part of the vanguard of the current charge into the unknowable,
and “you still can’t predict what it’s going to do.”
Eva Miranda, a mathematician at the Polytechnic University of Catalonia (UPC) in Spain, calls undecidability a “next-level chaotic thing.”
https://www.wired.com/story/next-level-chaos-traces-the-true-limit-of-predictability/?utm_content=buffer6602d&utm_medium=social&utm_source=facebook&utm_campaign=buffer
KilleansRow 🇺🇲 🇺🇦🍀A great little article. Why pay attention to this? Well…some of the relationships between #Computability, #Undecidability, #Church-#Turing , #SuperDeterminism, #Nonfalsifiability and bits like the #SimulationHypothesis indicate deeper complexities and connections. Is there some underlying dimensionality or topology yet to emerge ? It seems likely, but vexatious
Via @QuantaMagazine
‘Next-Level’ Chaos Traces the True Limit of Predictability
https://www.quantamagazine.org/next-level-chaos-traces-the-true-limit-of-predictability-20250307/
‘Next-Level’ Chaos Traces the True Limit of Predictability | Quanta Magazine
In math and computer science, researchers have long understood that some questions are fundamentally unanswerable. Now physicists are exploring how even ordinary physical systems put hard limits on what we can predict, even in principle.
Marcel FröhlichFernando Rosas (unfortunately not on Mastodon) asked on bsky:
"Has anyone figured out what exactly is the relation between the ideas of feedback, recurrence, and self-reference?"
A really interesting question.
He pointed to this paper for ideas: https://arxiv.org/abs/1711.02456
"Self-referential basis of undecidable dynamics: from The Liar Paradox and The Halting Problem to The Edge of Chaos"
I did some desk research and found this cool paper:
https://arxiv.org/abs/1112.2141
"Resolving Gödel's Incompleteness Myth: Polynomial Equations and Dynamical Systems for Algebraic Logic"
that argues there is no essential incompleteness in formal reasoning systems if you look closely enough (using a more elaborate formalism based on polynomial equations to represent and evaluate logical proposition).
I wonder if analogous construction could be created for related theorems like the halting problem in computability theory.
#DynamicalSystems #IncompletenessTheorem #PolynomialEquations #HaltingProblem #Undecidability #SelfReference #Recurrence
Self-referential basis of undecidable dynamics: from The Liar Paradox and The Halting Problem to The Edge of Chaos
In this paper we explore several fundamental relations between formal systems, algorithms, and dynamical systems, focussing on the roles of undecidability, universality, diagonalization, and self-reference in each of these computational frameworks. Some of these interconnections are well-known, while some are clarified in this study as a result of a fine-grained comparison between recursive formal systems, Turing machines, and Cellular Automata (CAs). In particular, we elaborate on the diagonalization argument applied to distributed computation carried out by CAs, illustrating the key elements of Gödel's proof for CAs. The comparative analysis emphasizes three factors which underlie the capacity to generate undecidable dynamics within the examined computational frameworks: (i) the program-data duality; (ii) the potential to access an infinite computational medium; and (iii) the ability to implement negation. The considered adaptations of Gödel's proof distinguish between computational universality and undecidability, and show how the diagonalization argument exploits, on several levels, the self-referential basis of undecidability.
PCThank you! Wonderful essay on #Leibniz efforts to reconcile math with humanity.
Makes me think about #KurtGödel and his #Undecidability work.
