Chaitin’s Omega and an algorithmic phase transition

G.J., 1975, A theory of program size formally identical to information theory, J. Assoc. Comput. Mach., 22, 329, 10.1145/321892.321894 Turing, 1936, On computable numbers with an application to the entscheidungsproblem, Proc. Lond. Math. Soc. (2), 42, 230 Li, 1993 Goedel, 1931, Ueber formal unentscheidbare Saetze der Principia Mathematica und verwandter Systeme I, Monatshefte Fuer Math. Phys., 38, 173, 10.1007/BF01700692 Tadaki, 2002 Calude, 2006, Natural halting probabilities, partial randomness, and zeta functions, Inform. and Comput., 204, 1718, 10.1016/j.ic.2006.07.003 Baez, 2010 Zinn-Justin, 1989 Green, 1988 K. Tadaki, A statistical mechanical interpretation of algorithmic information theory, in: Local Proc. of Computability in Europe 2008 (CiE 2008) (University of Athens, Greece), June 15–20, 2008, pp. 425-434. Electronic Version: http://www.cs.swan.ac.uk/cie08/cie2008-local.pdf. Tadaki, 2012, Phase transition between unidirectionality and bidirectionality Tadaki, 2014, Phase transition and strong predictability, 340 Kolmogorov, 1963, On tables of random numbers, Sankhyā, 369 Solomonoff, 1964, A formal theory of inductive inference. Part I, Inf. Control, 7, 1, 10.1016/S0019-9958(64)90223-2 Levin, 1974, Laws of information conservation (nongrowth) and aspects of the foundation of probability theory, Probl. Pereda. Inf., 10, 30 Kolchinsky, 2020, Thermodynamic costs of turing machines, Phys. Rev. Res., 2, 10.1103/PhysRevResearch.2.033312 Landauer, 1961, Irreversibility and heat generation in the computing process, IBM J. Res. Dev., 5, 183, 10.1147/rd.53.0183 Yuri I. Manin, 2008, Zipf’s law and avoidance of excessive synonymy, Cogn. Sci., 32, 1075, 10.1080/03640210802020003 Manin, 2014, Complexity vs energy: theory of computation and theoretical physics, J. Phys. Conf. Ser., 532 Yuri I. Manin, 2015 Cubitt, 2015, Undecidability of the spectral gap, Nature, 528, 207, 10.1038/nature16059 Bausch, 2018 Fortnow, 2003, One complexity theorist’s view of quantum computing, Theoret. Comput. Sci., 292, 597, 10.1016/S0304-3975(01)00377-2 Polyakov, 1987, Gauge fields and strings, vol. 3 Gross, 1990, Nonperturbative solution of the ising model on a random surface, Phys. Rev. Lett., 64, 10.1103/PhysRevLett.64.717 Moore, 1992 Schmidhuber, 1993, Exactly marginal operators and running coupling constants in 2-D gravity, Nuclear Phys. B, 404, 10.1016/0550-3213(93)90483-6 Schmidhuber, 1997, A computer scientist’s view of life, the universe, and everything Minsky, 1966