Disclaimers

This is a stub. I am having exams right now and do not have the time to write the full article. I'll update (not any time soon) after I've resolved the problems in this article.

The original post was supposed to be part of my "Meditations in Ontology" sequence (I planned on starting the sequence next year at earliest, probably later). I'll probably write a few other stubs to address the recent discussion about existence and truth.

I have learned neither computability theory nor information theory; if I make a mistake somewhere, please correct me.


There has been recent discussion about what it means to "exist". I realised that I have an answer to that question, and decided to briefly explain it here.

Useful Concepts

Object

For the purposes of this post it is sufficient to understand an object as "anything".

Structural Equivalence

Two systems are structurally equivalent if they are composed of the same components.

Functional Equivalence

Two systems are functionally equivalent if they have the same domain, the same range and the same image for all inputs.

Two structurally equivalent systems are functionally equivalent, yet two systems can be functionally equivalent and structurally similar. Sometimes, the semantic content of a concept refers to its function (e.g a clock). At other times, the semantic content might refer to its structure (e.g an atom). Yet still, some concepts may be defined according to both form and structure (e.g a gold watch).


Simulation

When we say that one object simulates another object , we say that (or a specific output of (if is a computational system) is a perfect fidelity model of . That is, in all ontologies (or said output of ) and are indistinguishable and interchangeable.

A Note on Computation

The output of a computation has no inherent meaning. There is no global semantic content to the output of a given computation. When I run a program, the stream of binary code sent to the output devices have no meaning. Only after they have passed the output device, and have been translated from binary to a language I understand, can I "read" the information therein. If I thought in binary, perhaps my monitor would just display the binary stream directly.

Observer

For a given computational process, the semantic content of the output is defined relative to an observer that would read that output and gain information from it. The output may need to be interpreted to the observer.

An observer is an agent who "reads" (an interpretation of) the output of a computation and extracts information from it.

It is important to note that the observer of a computation is external to that computation. Whatever observes a simulation is not itself inside the simulation (it maybe represented in the simulation, but it is not part of the simulation itself).

Furthermore, it should be noted that there is a set of correct interpretations for each output given and observer pair. Whenever we say "interpretation", we refer to a member of this set.

For a given output, we might imagine how different agents may understand the output of it was interpreted into their language.

Let be the set of all agents.

.

is the meaning of V to α. The domain of "" is the set of all objects.

Computational Simulation

According to our definition of simulation, a computational system simulates an object if a given output of is a perfect fidelity model of .

is a given output of . Let be the input to such that simulates .

Local Simulation

locally simulates for if and only if .

That is has the same meaning as to .

Global Simulation

globally simulates (or just " simulates ") if and only if

That is has the same meaning as to all agents.

The output of becomes the input to the program which then translates into whatever language the agent uses and them "runs" it on the agent's own processor.


Information Theoretic Ontology

Axiom of Computability

The universe is computable. This means that it is possible to simulate this universe on an infinite state universal Turing machine with unbounded processing power. This simulation does not need to be physically realisable, and only needs to be logically realisable. We shall refer to this Turing machine which simulates the Universe as the God Turing machine (abbreviated ).

is capable of simulating every other Turing machine. As for whether can simulate itself, I think it should be able to. If it is possible without breaking the Turing machine model, can simulate itself. If it's not, I'll fix that when I'm stronger.

From this axiom, we shall concern ourselves only with computable (not necessarily physically so—if physical infeasibility is the only reason why something cannot be computed, then it is computable) ontologies.

If we accept the above axiom, then some interesting results follow. Two Turing machines may run programs that are structurally dissimilar (different binary representations), but functionally equivalent. As the programs are functionally equivalent, the Turing machines are for all intents and purposes running the same program.

Information content

The Kolmogorov complexity of an object is the length of the shortest program that would produce that object is output.

The information content of an object is that shortest program that produces the object and output.

We shall denote the information content of an object as . The Kolmogorov complexity of |.

Where:

'' represents the reference Turing machine (we shall denote using '').

represents the length of .

Equivalence Class

For a given object , and a given Turing machine , the -program-equivalence class of is the set of all programs which when run on produce as output, this is denoted .

Minimal Equivalence Class

For a given program-equivalence class of a given object , the minimal program-equivalence class of (denoted ) is the set of all programs in such that there does not exist another program in with length shorter than that program.

Where:

represent arbitrary programs,

is the binary length of .

Axiom of Information Equivalence

For any two objects and .

'' means that in (and any ontology simulates), and are the same object.

Constraint of Consistency

For a given object , there may exist more than one shortest program (. Any of these programs in may be selected as the information content of that object, as long as they satisfy the constraint of consistency:

In English:

If there exists two objects X and Y for whom the set of programs that produce each of them are equal, and more than one program has length that is minimum in specified set, then the information content of the object can be any such program in the set, and the information content of Y would be the same as the information content of X.

Is

Existence

There are two senses in which an object can exist.

  1. An object exists in a given model.
  2. An object exists in reality.

Let a given output of on input be denoted . Let be the input to such that the output of is some model .

Let be the input to such that it simulates reality.

Then to answer the above questions:

  1. exists in if and only if is a substring of .
  2. exists in reality if and only if is a substring of .

It is possible for two different programs to have the same binary code if they are interpreted differently. This, it is important to specify that all Turing machines we are concerned with each use only one language in their operations.

It is possible to expand this to denote what it means to exist at a particular location (time, space, etc) but I don't know physics, so I don't know how would represent that.


Problems/Issues

  1. Is the universe computable? If the axiom of computability is false, then the ontology is useless.
  2. Can the simulate itself? The relevance of this may not be apparent now, but the answer to this question is relevant to the rest of my ontology.
  3. How do we define existing at a particular location? A notion of existence such that exists if it existed in the distant past is not what we want is it?

Author's Note

This is a stub of the full article (a task I'm far from being able to undertake yet). However, I resolved some non-trivial problems using this ontology, so I feel this is a very handful paintbrush to have.

I don't want to end up making this too long to be a stub, but too short/not rigorous enough to be the full article. Given that I can't write the full article yet, I tried to make the post as short as possible. The focus on brevity (of necessity) sacrificed pedagogical value, and thus a lot of heavy lifting in grokking this is done by my understanding of the concepts.

I'll provide examples, clarifications, deeper explanations, etc in the comments as needed. I'll do my best to address any points you make. However, as I'm currently writing exams, I'm not sure how quickly I would be able to respond.

New Comment
18 comments, sorted by Click to highlight new comments since:
[-]gjm20

So, if I've understood correctly, you say that X exists in reality when the following holds. (1) Let C be the shortest program whose output is X. (2) Suppose that our universe is the output of a machine G with input Q. (3) Then X exists in reality iff C is a substring of the output of G with input Q.

Note that the output of G with input Q is our universe, or some symbolic representation of it. So you're saying that X exists in reality precisely when the shortest program that generates it is a substring of (an appropriate representation of) our universe.

I don't see any reason why anything like this should be true.

On the face of it, it has something like a type error: you're looking for a particular program in the output of a program. Of course this isn't necessarily a type error; there are computers in the universe, it's sometimes useful to feed a program itself as input, there are programs that write programs, etc. But I'd like to see some actual justification for it because it seems implausible.

Similarly implausible: your setup seems like it's going to make essential use of G, but then in the actual definition G appears only as G(Q) which turns out to be (kinda) the same thing as the universe, so G has disappeared again.

(There are other things in your proposal that make me uneasy. A few examples: "The shortest program" may not be unique. What G produces will be some sort of symbolic representation of our universe and there will be vastly many different such representations, which will have different things as substrings. The is-a-substring-of relation is not usually a useful one to apply to programs.)

I have edited it and I think I've satisfactorily answered the points you raised. This is meant to be a stub, so I focused on brevity—necessarily at the expense of pedagogy—but I would be willing to address any concerns you have.

A lot of heavy lifting is done by my understanding of the concepts. I'm not sure how much I can explain the ontology without writing the full article (a task I'm not ready to do yet), but I would do my best.

[-]gjm30

I can wait until you write the thing up properly. Advance warning: it doesn't seem to me that any of the changes you've made do anything to address my main criticism (I don't see any reason at all why "X exists iff the shortest program generating it appears somewhere in the output of a machine that simulates the universe" should be anywhere near true); your (if I've understood right) arbitrary choice of which shortest program to use as "information content of X" when there's ambiguity means that what things "exist" is likewise arbitrary; your notion of interpretation seems to me to be given more responsibility than it can actually bear (e.g., you haven't said anything about what restrictions there are on what things an agent can interpret in what ways...). But, again, I'm happy to wait until you've made your proper writeup before arguing about any of this :-).

[-]gjm20

Apologies for the double-post. LW2 was being unresponsive, and of course in that situation the choice you make (try again, or don't) is always the wrong one :-).

Remember the notion of structural and functional equivalence.

Consider X, we compute the shortest program produces X as output. If Y is structurally equivalent to X, then Y is functionally equivalent to X.

If Y is structurally equivent to X, then the information content of Y and X are the same.

Given that a certain object exists, what can be said to exist is any object structurally equivalent to that object. If X, X', and X'' all have the same information content, and C_G(X) is in G(Q), then X, X' and X'' can each be said to exist. They are the same object.

Restrictions on interpretation should be added as a problem to be honest. Hopefully, the global criteria for simulation resolves thst.

[-]gjm20

I think you're addressing a concern that's kinda dual to the one I actually have. Suppose we have an object X. We pick some shortest program that implements X -- call it P -- and then say that "X exists" if we can find P somewhere in (the relevant symbolic representation of) the universe. (I reiterate that this criterion seems obviously wrong to me, but never mind; that's not my concern right now.) If we have another Y equivalent to X, then your definitions say that we should use P as "the information content of" Y as well as X. Likewise for anything else equivalent to these. There may be some other shortest program P2 that implements (equivalents of) them all, and P2 is completely ignored here. Now, my concern is this: whether we pick P or P2 is an arbitrary decision, but the universe -- i.e., the output of "G(Q)" -- may contain one and not the other. So whether X (along with Y, Z, etc.) "exists" is determined by this entirely arbitrary choice. That seems to me rather unsatisfactory.

Again: I'm happy to wait for further enlightenment until you have time to write the thing up properly. I'm replying to you because you replied to me :-), but would not want you to feel any pressure to keep responding here while you're busy with other things.

There may be some other shortest program P2 that implements (equivalents of) them all, and P2 is completely ignored here.

If P2 is shorter than P, then according to the definition of information content, P2 would be selected instead of P.

Again: I'm happy to wait for further enlightenment until you have time to write the thing up properly. I'm replying to you because you replied to me :-), but would not want you to feel any pressure to keep responding here while you're busy with other things.

My plan prior to starting my "Meditations on Ontology" sequence:

Complete a course (autodidactry) in analytical philosophy.

  • Learn information theory.
  • Learn computability theory.
  • Learn causality.
  • Learn relevant maths.

I graduate next year, so there's hope.

[-]gjm20

I wasn't suggesting a shorter P2 but an equally short P2.

The constraint of consistency means that all programs equivalent to a certain program would be represented by one single program. I think it may be useful to define an equivalence clasd for each program. For each equivalence class, one member of that class would be substituted for any occurrence of the other members of the class.

[-]gjm20

Yes, I understand that just one of P and P2 would be taken as representative. And I'm saying that then the question of whether X (the thing computed by P and P2) "exists" may have a different answer depending on whether we arbitrarily picked P or P2, and that that seems unsatisfactory.

It would not have a different answer. If P is chosen for Y, and X and Y belong to the same equivalence class, then X would be computed as P, and vice versa for P2.

P.S: sorry for the late reply.

[-]gjm20

I think one of us is misunderstanding the other. I'm not saying that two equivalent things would be treated differently. That is, I'm not concerned that we would get different answers to "does X exist?" and "does Y exist?" with X and Y being equivalent.

My concern is a different one. In order to decide whether (say) X exists, we have to make an arbitrary choice of whether to use P or P2. We will then use the same choice for Y as well, so X and Y will come out the same way, and that's fine. But that arbitrary choice will make a difference to whether or not we say that X and Y exist, and that is what bothers me.

(I said much the same thing six comments upthread and it seems like I was misunderstood then too. Or perhaps I have been misunderstanding everything you've been saying since then :-).)

But that arbitrary choice will make a difference to whether or not we say that X and Y exist, and that is what bothers me.

I do not understand how this follows from:

In order to decide whether (say) X exists, we have to make an arbitrary choice of whether to use P or P2. We will then use the same choice for Y as well, so X and Y will come out the same way, and that's fine.

If there's a problem, then it is the inference you're making from the second quote to the first. That is the cause of the misunderstanding. I would appreciate it if you explained why you think the arbitrary choice makes a difference whether an object exists (that is not supposed to happen, and I designed it so it wouldn't).

[-]gjm20

I am not sure what to say that might clarify further, but let me try again.

First of all, I am not making an inference from the second quote to the first. The second one is not there to support the first one. It is there because you seemed to be misunderstanding me, and I wanted to deal with the misunderstanding.

So let me see what I can say to support my objection.

First of all, your definition says (roughly) that the criterion for X to "exist" is: let P be "the" minimal program that implements X; then X exists iff P appears somewhere in "the output of G(Q)". Here G(Q) is a computer program that implements our universe given input Q; in other words, its output is (some sort of symbolic representation of) our universe.

Question: does the above paragraph correctly describe your intention?

Now, suppose there are in fact two minimal programs that implement X. Call them P and P2. Your definition says that we are supposed to pick one of them. (We are supposed to do this consistently, in the sense that if we pick P rather than P2, we should also pick P rather than P2 for anything else implemented by these programs. This is not directly relevant here, though.)

Question: does the above paragraph correctly describe your intention?

If the answers to my two italicized questions are correct, then:

If we choose P, then X "exists" iff P appears somewhere in (a symbolic representation of) our universe. If we choose P2, then X "exists" iff P2 appears somewhere in (a symbolic representation of) our universe.

There is no reason why these two propositions should be equivalent. So whether we choose P or P2 may make a difference to whether or not X "exists".

(This is, just to reiterate something I hope I made clear above, not my principal objection to your proposal as I understand it. One could work around this objection by saying e.g. that X "exists" iff there is some minimal program implementing X that appears in G(Q). My more fundamental objection is that it seems perfectly obvious to me that whether P appears in G(Q) has nothing whatever to do with whether X exists, because there is no reason why the universe should contain programs implementing all its objects.)

If we choose P, then X "exists" iff P appears somewhere in (a symbolic representation of) our universe. If we choose P2, then X "exists" iff P2 appears somewhere in (a symbolic representation of) our universe.
There is no reason why these two propositions should be equivalent. So whether we choose P or P2 may make a difference to whether or not X "exists".

As I understand this, the two propositions are equivalent. We do not arbitrarily pick P or P2 (we assume that one is picked and is picked consistently). What this means is that the G(TM) will also pick P or P2 consistently. If G(TM) outputs P, then it would never output P2 and vice versa. Only one of the members of the equivalence class become the shortest program, and that member represents the entire class everytime the class is invoked. So the shortest program will be computed by G consistently when simulating our universe.

My more fundamental objection is that it seems perfectly obvious to me that whether P appears in G(Q) has nothing whatever to do with whether X exists, because there is no reason why the universe should contain programs implementing all its objects.)

Do you agree that the universe can be simulated?

[-]gjm20

(Sorry about the long delay in replying.)

Yes, I agree that the universe can be simulated (or, more precisely, my guess is that it can be, the available scientific evidence suggests that it probably can be, and it's a convenient working hypothesis).

I'm afraid I don't at all understand your argument here. "If G(TM) outputs P, then it would never output P2 and vice versa" -- I have no inkling why that should be true. Why do you believe that G(TM) cannot output both of them on different occasions?

Examples, clarifications, etc would be in the comments.

I don't want to end up making this too log to be a stub, but too short/unrigorous to be the full article. Given that I can't write the full article yet, I'll try and make the post as short as possible.

I have an answer. I'll edit this post in a few hours (exam next hour) with my answer.