> From [EMAIL PROTECTED] Tue Feb 13 10:49:14 2001 > Subject: Re: Algorithmic TOEs vs Nonalgorithmic TOEs > > [EMAIL PROTECTED]: > > This constructive notion of formal describability is less restrictive > > than the traditional notion of computability, mainly because we do not > > insist on the existence of a halting program that computes an upper > > bound of the convergence time of p's n-th output bit. Formal > > describability thus pushes constructivism to the extreme, barely > > avoiding the nonconstructivism embodied by even less restrictive > > concepts of describability. > > It certainly tests the limits, since there's in principle no way of > knowing in general at any time whether a particular bit of the answer > on the tape is yet the "final answer". Sure. Still, each bit eventually stabilizes forever. Hence the entire bit sequence is constructively describable, and thus a potential universe history that we may not ignore - it might be ours. Example 1.1 [Pseudorandom universe] Let x be an infinite sequence of finite bitstrings x^1,x^2,... representing the history of some discrete universe, where x^k represents the state of the universe at discrete time step k, and x^1 the "Big Bang" (compare http://www.idsia.ch/~juergen/everything/node1.html ). Suppose there is a finite algorithm A that computes x^{k+1} (k \geq 1) from x^{k} and additional information noise^k (this may require numerous computational steps of A, that is, "local" time of the universe may run comparatively slowly). Assume that noise^k is not truly random but calculated by invoking a finite pseudorandom generator subroutine. Then x is describable because it has a finite constructive description. Example 2.1 [Pseudorandom universe based on halting problem] Let x be a universe history in the style above. Suppose its pseudorandom generator's n-th output bit PRG(n) is 1 if the n-th program of an ordered list of all possible programs halts, and 0 otherwise. Since PRG(n) is describable, x is too. But there is no halting algorithm computing PRG(n) for all n, otherwise the halting problem would be solvable, which it is not. Hence in general there is no computer that outputs x and only x without ever editing some previously computed history: http://rapa.idsia.ch/~juergen/toesv2/node7.html > I see how you could compute Omega: both create and run all Turing > machines in a diagonalized way, and each time one halts, increase the > approximation of the halting probability by the appropriate amount. > But you'd never be sure of even bits near the front, because some > running small machines might halt anytime, altering those early bits. Sure. But each bit of Omega will eventually stabilize forever. Omega is actually not so bad as it is enumerable - you won't even need a GTM for it, you can compute it on an EOM. GTMs are required, however, for constructively describable numbers even worse than Omega. See Theorem 3.3: http://rapa.idsia.ch/~juergen/toesv2/node14.html > > ... Machines with real-valued registers ... > > This does not lead outside the GTM realm as long as the indefinitely > > growing register contents are finite for each finite time step. > > Well, I was thinking they would have operations like reciprocal (or > maybe 1/(x+1) to limit the range) which could instantly generate > non-terminating expansions. More interestingly they might include > transcendental operations to generate non-repeating expansions. > Hey, they could even have the "Omega" operation, which loads > a register with Omega, all bits finalized. > > That certainly beats GTMs. Check out analytic TMs (Hotz, Vierke and Schieffer, 1995) and R-Machines (Blum, Shub, Smale, 1989): http://rapa.idsia.ch/~juergen/toesv2/node47.html The alphabet of such TMs is indeed real-valued instead of binary. This is beyond constructivism though. GTMs are at the extreme end of the constructive spectrum. They are beaten by nonconstructive devices only. But stuff describable by nonconstructive devices only does not even exist. Does it?

- Re: Algorithmic TOEs vs Nonalgorithmic TOEs juergen
- Re: Algorithmic TOEs vs Nonalgorithmic TOEs hpm
- Algorithmic TOEs vs Nonalgorithmic TOEs juergen
- Re: Algorithmic TOEs vs Nonalgorithmic TOEs juergen
- Re: Algorithmic TOEs vs Nonalgorithmic TOEs Stephen Paul King
- Re: Algorithmic TOEs vs Nonalgorithmic TOEs Russell Standish

- Re: Algorithmic TOEs vs Nonalgorithmic TOEs juergen
- Re: Algorithmic TOEs vs Nonalgorithmic TOEs juergen