Post #3650701

2026-06-25 22:21 UTC

While organizing some files today I came across my copy of Charles H. Bennett&#39;s &quot;On Random and Hard-to-Describe Numbers&quot; from 1979 (https://www.worldscientific.com/doi/abs/10.1142/9789812770837_0001). It discusses Chaitin&#39;s constant (https://en.wikipedia.org/wiki/Chaitin%27s_constant) for a programming language, which is the probability \(\Omega\) that a randomly-chosen program will compile. This is a real number between 0 and 1 which is definable but not computable. Bennett goes on to discuss the &quot;Cabalistic&quot; properties of \(\Omega\). Knowing the first few thousand digits of \(\Omega\) would allow one to decide practically all finitely refutable mathematical conjectures. Basically, \(\Omega\) is a very compact encoding of the Halting Problem (https://en.wikipedia.org/wiki/Halting_problem), so knowing its first \(n\) bits is enough to determine whether any program up to \(n\) bits in length would eventually halt. While there are some exceptions, many open problems in mathematics can be phrased in terms of the halting of some computer program of reasonably short length. (1/3) #math #mathematics #ComputerScience #hypercomputer #programming #microfiction #ScienceFiction #physics #BlackHole #ClosedTimelikeCurve #relativity #probability

Replies (1)

@caten@mathstodon.xyz 2026-06-25 22:21

When I learned about this as an undergraduate I started telling people the following story: Suppose that, simultaneously, two space-faring civilizations discover a naturally-occurring closed timelike curve (https://en.wikipedia.org/wiki/Closed_timelike_curve) around a nearby black hole. Suppose further that these civilizations both know that this structure can be used to build a hypercomputer (https://en.wikipedia.org/wiki/Hypercomputation), a machine that can perform an infinite number of classical computational steps in a finite amount of time. In order to make our story more realistic, we add the following constraints: (1) The hypercomputer can correctly perform an infinite calculation, but it must be described by a finite program. (2) The hypercomputer can access an arbitrarily large amount of memory during calculation, but there is a fixed finite size for its output after the infinite calculation is over. (3) A massive amount of resources are needed for each use of the hypercomputer. Perhaps it breaks after each use. (2/3) #math #mathematics #ComputerScience #hypercomputer #programming #microfiction #ScienceFiction #physics #BlackHole #ClosedTimelikeCurve #relativity #probability

Open ##3672591