> From: [EMAIL PROTECTED] > To: [EMAIL PROTECTED] > Subject: Re: Algorithmic TOEs vs Nonalgorithmic TOEs > Date: Fri, 9 Feb 2001 19:26:23 EST > > [EMAIL PROTECTED]: > > Nobody will ever be able to fully describe anything that is not > > computable in the limit by a general Turing Machine. > > It hasn't been proven that Turing computability is ultimate in > computability, only its equivalence to other proposed models of > computability with finite descriptions. It seems unlikely today, but > tomorrow someone could come up with an organization that can't be > simulated on a Turing machine.
Much of http://rapa.idsia.ch/~juergen/toesv2/ is about things uncomputable on traditional Turing machines. That's why we need to introduce General Turing Machines or GTMs: http://rapa.idsia.ch/~juergen/toesv2/node6.html > Somewhat unsatisfactory possibilities have been around, that > can do uncomputable things: > > Turing machines with various oracles (with a Chaitin's Omega oracle, a > machine can solve the halting problem and compute many uncomputable > numbers). GTMs are indeed the ultimate in computability as they can compute not only enumerable numbers such as Omega but also certain nonenumerable numbers. Since "computable" is often used for "computable by a halting program", let me use "formally describable" for "GTM-computable in the limit", and cut and paste from http://rapa.idsia.ch/~juergen/toesv2/node2.html : An object X is formally describable if a finite amount of information completely describes X and only X. More to the point, X should be representable by a possibly infinite bitstring x such that there is a finite, possibly never halting program p that computes x and nothing but x in a way that modifies each output bit at most finitely many times; that is, each finite beginning of x eventually converges and ceases to change. 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. > Machines with true real-valued registers. The registers would be > initialized in a finite way, say to 0, but operations could produce > register contents corresponding to infinite expansions. I think there > are "algorithms", like the sieve of Erastothenes, on such infinite > binary expansions, able to do work in single steps that would take > Turing machines forever. Halting-type problems can be solved by > computing all possible cases along the expansion, then doing a > zero/nonzero test on the final answer, to check for the presence or > absence of a single bit anywhere. This does not lead outside the GTM realm as long as the indefinitely growing register contents are finite for each finite time step. You are implicitly referring to "weak decidability". Traditionally, decidability of some problem class implies there is a halting algorithm that prints out the answer, given a problem from the class. We relax the notion of decidability by allowing for infinite computations on EOMs or GTMs whose answers converge after finite yet possibly unpredictable time. Essentially, an answer needs to be correct for almost all the time, and may be incorrect for at most finitely many initial time steps: http://rapa.idsia.ch/~juergen/toesv2/node9.html The halting problem is weakly decidable. So is the problem of deciding whether number theory is consistent. After finite time (but you won't know when) you'll have a correct answer that won't change ever. Interestingly, there are problems that are not weakly decidable (Theorem 2.1). Algorithmic TOEs are about universes describable via GTMs, and probabilities computable in the limit by GTMs. Nonalgorithmic TOEs are something else, something beyond describability.
