Ben, Unfortunately, this response is going to be (somewhat) long, because I have several points that I want to make.
If I understand what you are saying, you're claiming that if I pointed to the black box and said "That's a halting oracle", I'm not describing the box directly, but instead describing it in terms of a (semi)formal system in my head that defines "halting oracle". This system is computable. This seems to fit back with the comment I made about William Pearson's system: we don't assume that the universe is computable, instead we just assume that our mental substrate is. But, we need to be careful about what "computable" means here. Things like a mandelbrot set rendering are "computably enumerable", which is formally separated from "computable", but still easily implemented on a computer. The same is true of first-order theories that describe "halting oracle" and related notions. Technically these are not "computable", because there is no halting criteria (or, in the case of the mandelbrot renderer, no halting criteria *yet*, although many mathematicians expect that one can be formulated.) We can list positive cases (provably halting/nonhalting programs, provably escaping points) but we have no way of deciding when to give up on the stubborn points. A third type of computability is "computably co-enumerable", which is what the halting problem is. I imagine you know the definition of this term already. So, halting-related things such as "halting oracles" have no "computable" description, but they do have a description-implementable-on-a-computer. Unfortunately, AIXI does not use models of this variety, since it only considers models that are "computable" in the strict technical sense. But, worse, there are mathematically well-defined entities that are not even enumerable or co-enumerable, and in no sense seem computable. Of course, any axiomatic theory of these objects *is* enumerable and therefore intuitively computable (but technically only computably enumerable). Schmidhuber's super-omegas are one example. Concerning your statement, "It is not clear what you really mean by the "description length" of something uncomputable, since the essence of uncomputability is the property of **not being finitely describable**." That statement basically agrees with the following definition of meaning: "A statement is meaningful if we have a (finite) rule that tells us whether it is true or false." The idea of "finite rule" here is a program that takes finite input (the facts we currently know) and halts in finite time with an output. This agrees with the formal definition of "computable", so that meaningful facts and computable facts are one and the same. Here is a slightly broader definition: "A statement is meaningful if we have a (finite) rule that tells us whether it is true." This agrees instead with the definition of enumerable. Or, the "scientific testability" version: "A statement is meaningful if we have a (finite) rule that tells us whether it is false." This of course agrees with the definition of co-enumerable. Now here is a rather broad one: "A statement is meaningful if we have a (finite) rule that tells us how we can reason if it is true." So, each statement corresponds to a program that operates on known statements to produce more statements; applying the rule corresponds to using the fact in our reasoning. So the direct consequences of a statement given some other statements are computable, but the truth or falsehood is not necessarily. As it happens, this definition of meaning admits horribly-terribly-uncomputable-things to be described! (Far worse than the above-mentioned super-omegas.) So, the truth or falsehood is very much not computable. I'm hesitant to provide the mathematical proof in this email, since it is already long enough... let's just say it is "available upon request". Anyway, you'll probably have some more basic objection. --Abram On Mon, Oct 20, 2008 at 10:38 PM, Ben Goertzel <[EMAIL PROTECTED]> wrote: > > > On Mon, Oct 20, 2008 at 5:29 PM, Abram Demski <[EMAIL PROTECTED]> wrote: >> >> Ben, >> >> "[my statement] seems to incorporate the assumption of a "finite >> period of time" because a finite set of sentences or observations must >> occur during a finite period of time." >> >> A finite set of observations, sure, but a finite set of statements can >> include universal statements. > > Ok ... let me clarify what I meant re sentences > > I'll define what I mean by a **descriptive sentence** > > What I mean > by a sentence is a finite string of symbols drawn from a finite alphabet. > > What I mean by a *descriptive sentence* is a sentence that is agreed by > a certain community to denote some subset of the total set of observations > (where all observations have finite precision and are drawn from a certain > finite set). > > So, whether or not a descriptive sentence contains universal quantifiers or > quantum-gravity > quantifiers or psychospirituometaphysical quantifiers, or whatever, in the > end > there are some observation-sets it applies to, and some it does not. > > Then, what I claim is that any finite set of descriptive sentences > corresponds > to some computable model of reality. One never needs an uncomputable > model of reality to justify a set of descriptive sentences. > >> >> >> "Fractal image compression is computable." >> >> OK, yea, scratch the example. The point would possibly be valid if >> fractal compression relied on a superset of the Mandelbrot set's math, >> since the computability of that is still open as far as I know. > > No ... because any algorithm that can be implemented on a digital computer, > can obviously be described in purely computable terms, using assembly > language. Regardless of what uncomputable semantics you may wish to > assign to the expression of the algorithm in some higher-level language. > >> >> "Based on a finite set of finite-precision observations, there is no >> way to distinguish Wei Dai's black box from a black box with a Turing >> machine inside." >> >> Sure, but the more observations, the longer the description length of >> that turing machine, so that at some point it will exceed the >> description length of the uncomputable alternative. > > We have to be careful with use of language here. > > It is not clear what you really mean by the "description length" > of something uncomputable, since the essence of uncomputability > is the property of **not being finitely describable**. > > One can create a Turing machine that proves theorems about > uncomputable sets ... i.e., that carries out computations that > we can choose to interpret as "manipulating uncomputable sets." > > Just as, one can create a Turing machine that carries out computations > that we interpret as differential calculus operations, acting on > infinitesimals. > > However, even though we call them "uncomputable", in reality these > computations are computational, and their so-called "uncomputability" > is actually just a mapping between one computable formal structure > and another (the first formal structure being the algorithms/structures > carrying out > the computations ... the second formal structure being the formal theory > of computability, which is itself a finite set of axioms that can be > manipulated by a Turing machine ;-) ... > > There is no such thing as an uncomputable procedure with a short > description length (where descriptions are finite concatenations of > symbols from a finite vocabulary). There are however procedures with > short description lengths that have interpretations in terms of > uncomputability -- > where these interpretations, if they're to be finitely describable, must > also be computable ;-) > > -- Ben G > > > > > > ________________________________ > agi | Archives | Modify Your Subscription ------------------------------------------- agi Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/ Modify Your Subscription: https://www.listbox.com/member/?member_id=8660244&id_secret=117534816-b15a34 Powered by Listbox: http://www.listbox.com
