Truth Tables
post by johnlawrenceaspden · 2013-12-12T22:16:00.190Z · LW · GW · Legacy · 7 commentsContents
Self Evident Truths Truths Consequence TT(1) TT(2) Towards Infinity... But Not Beyond, (Or Even As Far As) I Find This A Bit Worrying, Because: Exercises None 7 comments
Summary: There's a short program that can run all possible programs, OMG
Alternative Summary: Just about any universe that can exist must contain ours, OMG.
I was thinking about diagonalization arguments. Does this make any sense? Can anyone debug it for me?
Self Evident Truths
The universe is computable.
All computations can be performed by Turing Machines.
The mind is made out of atoms.
The name of the empty string is epsilon.
Truths
Binary Strings are enumerable : epsilon, 0, 1, 00, 01, 10, 11, 000, ....
There's a way of converting binary strings to Turing machines and back again. It gets all Turing machines.
Consequence
Consider tables TT(n), which are numbered by binary strings along the top and side, representing turing machines and inputs respectively.
Construct a series of finite triangular tables which are defined iteratively as follows:
TT(1)
To construct the first table, we need one element, the top left, which corresponds to the turing machine epsilon working on the input string epsilon.
Convert the string epsilon to its corresponding turing machine, which has no states and no transition rules, and which therefore halts immediately without accepting.
The value of TT(1)(epsilon,epsilon) is therefore F0 (Fail after no steps).
eps
eps F0
That's it for TT(1).
TT(2)
TT(2) will have three cells, the topleftmost three
To construct the second table, consider again the element at the top left. Since it represents a halted state, copy it verbatim from the last table.
Then consider the element corresponding to (epsilon,0) , or row epsilon, column 0, or (TM(epsilon), "0")
Again TM(epsilon) is either a machine with no states, or an invalid specification, and so it halts immediately on the input 0.
For the third step in constructing the second triangle, consider (TM("0"), epsilon).
TM("0") is another dud. It halts immediately without accepting.
So TT(2) is the table
eps 0
eps F0 F0
0 F0
Towards Infinity...
It should be reasonably clear how to continue the construction of these tables
For instance TT(3) looks like
eps 0 1
eps F0 F0 F0
0 F0 F0
1 F0
Eventually we will reach a row whose string represents a TM which does something other than halt immediately without accepting.
As an example of what to do then, consider the string 1001111, which is the 207th string.
In the usual encoding, this string will represent the TM with start state 0, and transition function delta(0,B)=(0,0,L).
The first time we consider the 207th row will be when we calculate TT(207), the 207th triangular table.
The first cell we consider in that row will be ("1001111", epsilon). Since 1001111 represents a valid machine, we construct the Instantaneous ID (epsilon,0,epsilon), which represents a machine in state 0 with a blank tape.
That's the value of TT(207)("1001111",epsilon).
When we construct TT(208), we take that ID from TT(207), and execute one step. In this case, the machine head moves one step left, writing a zero, and so the instantaneous ID becomes
(epsilon,0,0) (State zero, tape reads ...0...., head just to the left of the zero)
And so on. The values of TT(n)("1001111",epsilon) are undefined for n<206, since the tables are not that large, but for n=207 onwards, they are:
(epsilon,0,epsilon), (epsilon,0,0), (epsilon,0,00), (epsilon,0,000), and so on, with the tape head moving ever leftward, leaving a run of zeros behind it.
Other strings may represent TMs that do things that are even more interesting.
But Not Beyond, (Or Even As Far As)
As we construct the successive tables, they become larger and larger. Some cells
will stabilize after a finite number of steps, either accepting or
rejecting their input strings, at which point their contents become
either F??? or A??? where ??? is the number of steps taken.
Some cells will loop. By comparing the instantaneous state of the table with the state of the cells in all previous tables, loops can be detected. We can mark them as loops, continue computing as before, or re-use the values in the previous tables to avoid performing the computations again.
And some cells, like the ones at ("1001111", epsilon) will keep producing new instantaneous IDs, without looping.
But every TT(n) is a finitely computable object. Indeed the program to compute them all is very short and will run on any computer worthy of the name.
I Find This A Bit Worrying, Because:
As we continue to construct the successive tables, we will perform every conceivable computation.
We will simulate in precise detail every possible world, universe and multiverse. Even though our computer is not quantum, we will simulate all quantum computations.
In particular, if you believe that you are a computation, or that simulation of your brain is equivalent to your existence, then you will be present in the computation, with exactly as much free will, and with your behaviour as precisely determined, as it ever was or will be.
Some of you will live in universes in which artificial intelligences rise and successfully paperclip everything.
Some of you will live in universes where friendly AIs are built, if that is possible.
It will not be possible for these copies to tell which copy they are, and so they will not be able to tell what is about to happen, or what has happened. Any more than you can.
There will be hells and paradises.
In some universes, copies of you will set programs running to calculate the successive triangular tables TT(n), and they will keep adding memory to their computers as needed (only actually one extra storage location per step of computation, at worst).
And so the sequence of finite truth tables will contain itself, as well as everything else. Everything that has ever happened will happen again. You will be reborn and live and possibly die.
You will not know whether you are in the 'base universe', or in the computation. If that even means anything.
And every computation that occurs as part of this great computation is utterly "Beyond the Reach of God".
Exercises
1/ It will take me about a day, a packet of cigars and a machine full of coffee to write this program and start it running. That is what I am doing now. When I start it running, will I have done a bad thing? If someone were to stop me before the program started running, would that make any difference to anything important?
2/ Can anything except what is computed by this program be said to exist in any sense? Continua, and sets of all sets, and so on, are very problematic. And if the human mind is itself a computation , contained in a universe which itself is a computation, how can we think of or interact with any non-computable thing?
3/ Does the ultimate Truth Table, which the finite tables TT(n) approach as the process continues, exist? What does that question mean? The values of many of its cells are determined. Many of them are not computable. The ratio is unclear.
4/ We can perform the initial stages of this computation with a finite computer with finite memory. At no point does the amount of memory required become infinite. If the computational power of the universe is infinite, then it can contain not only itself but every other thing. If the computation power of the universe is finite, where does that number come from?
5/ The program is very short. Any randomly chosen computation has a good chance of being it. It would probably be very hard to construct an interesting universe which did not contain every possible universe and person.
6/ Does it make any sense to talk about 'not being part of this computation'?
7 comments
Comments sorted by top scores.
comment by DanielLC · 2013-12-13T04:16:49.864Z · LW(p) · GW(p)
The universe is computable.
Not self-evident. It may turn out that the fine structure constant is somehow related to Chaitin's constant, which is uncomputable. Or it could be a completely unrelated computable number.
All computations can be performed by Turing Machines.
If by "computation", you mean "something that can be done on a turing machine", then this is a tautology. If not, I'd say it's false. The halting problem cannot generally be solved on a Turing Machine.
The mind is made out of atoms.
Not self-evident.
The name of the empty string is epsilon.
That's a definition, not a self-evident truth.
1/ It will take me about a day, a packet of cigars and a machine full of coffee to write this program and start it running. That is what I am doing now. When I start it running, will I have done a bad thing? If someone were to stop me before the program started running, would that make any difference to anything important?
If you run it forever, maybe. If you only run it for the lifetime of the universe, it's not likely to do anything important.
2/ Can anything except what is computed by this program be said to exist in any sense?
Sure. That program only deals with things that are computable. If the fine structure constant is uncomputable, then it exists, but is not computed by that program.
3/ Does the ultimate Truth Table, which the finite tables TT(n) approach as the process continues, exist?
I doubt it exists in any physically real sense, but I have no way if knowing. Mathematically speaking, it can be said to exist. Some suggest that it existing mathematically makes it something real that can be experienced, but I disagree.
What does that question mean?
I assume you're either asking if it's physically real, or if it exists in some mathematical sense.
If the computational power of the universe is infinite, then it can contain not only itself but every other thing.
Not necessarily every other thing. A computer that can run an infinite number of steps in a finite time can be said to have infinite computational power, yet it cannot explicitly state every function from R to R. It can only have as many states as there are real numbers, but there are more such functions.
If the computation power of the universe is finite, where does that number come from?
You could work it out from how the universe works. If our universe was finite and non-expanding, we could calculate it by looking at the maximal entropy state and subtracting the current entropy. That is the highest number of unreversible computations that can be done in the universe. Unfortunately, our universe is a bit more complicated than that.
The program is very short. Any randomly chosen computation has a good chance of being it.
It's not astronomically low. It's still on par with winning the lottery. A sufficiently large program certainly has a good chance of including it, but we don't know how large our program is. Also, regardless of the size of the program, there's a good chance of it halting before it gets to the part where it calculates everything.
It would probably be very hard to construct an interesting universe which did not contain every possible universe and person.
No it wouldn't. A universe of finite size would work. For example, Conway's game of life on a torus.
6/ Does it make any sense to talk about 'not being part of this computation'?
Yes. Chaitin's constant is not part of this computation.
Replies from: johnlawrenceaspden↑ comment by johnlawrenceaspden · 2013-12-16T19:44:08.912Z · LW(p) · GW(p)
Daniel, thanks for your very detailed reply. I shouldn't have said 'Self-evident Truths'. The only self evident truth that I know is 'all men are created equal', and that's not true. So I was using it to mean 'assertions'. Which was a stupid thing to do. I am ever tempted to rhetorical slyness over clarity.
I don't find myself forced to believe in uncomputable things in the same way that I find myself forced to accept the existence of countable infinite sets . I've always been really sceptical about the 'real numbers'.
People win the lottery every day!
No it wouldn't. A universe of finite size would work. For example, Conway's game of life on a torus.
Yes, that would be interesting, especially if the torus were very large. I retract that sentence. I think what's bugging me is that a TM with a finite tape seems more complicated than a TM with an infinite tape. If the finiteness is large, then there's more information in the size of the constant than there is in the machine. And in fact I believe that some very simple systems are turing equivalent.
I think my argument is something like 'If you let countability in at all, then you've probably got everything. Over and over again.'
Replies from: DanielLC↑ comment by DanielLC · 2013-12-16T20:29:42.430Z · LW(p) · GW(p)
I don't find myself forced to believe in uncomputable things in the same way that I find myself forced to accept the existence of countable infinite sets .
I'm not saying that uncomputable things exist. I'm just saying that they might.
I think what's bugging me is that a TM with a finite tape seems more complicated than a TM with an infinite tape.
So? Just because the computer can run forever doesn't mean that the program never halts or repeats.
Also, Occam's razor doesn't work that way. If you add a constant of a specific value, that makes it less likely because the probability has to be split over all possible values, and it's unlikely to be that specific one. If you're just suggesting that there is a constant, this does not apply.
comment by [deleted] · 2013-12-12T22:28:47.413Z · LW(p) · GW(p)
It would probably help if you explained what the tables were actually supposed to be, rather than hoping that the reader can deduce it from the construction. Is an entry in TT(n) supposed to represent the state of some turing machine with some input after n steps?
In any case, it looks like mostly you're using a whole lot of words to get across the idea that a program can dovetail running all possible programs.
For the "omg we're just computer programs what if I run it" part, note that you (or anyone in this universe) aren't actually going to run your program long enough to actually simulate anyone. Whether programs you don't run can experience anything is an unsolved philosophical problem that people who aren't me may want to go on about at length.
Replies from: johnlawrenceaspden↑ comment by johnlawrenceaspden · 2013-12-12T22:54:06.933Z · LW(p) · GW(p)
Khoth, yes absolutely.
I don't know why, but until I actually thought about what the diagonal argument means in terms of Turing machines I hadn't seen the horrible fridge logic of 'Even the simplest things that can exist must contain everything that can exist, and if that's not what we are, there must be an enormous coincidence going on'.
And all you need to explain the existence of everything that can possibly interact with us is one turing machine, which doesn't need to be infinite.
And things like the real numbers aren't. And it doesn't matter if we're a simulation or not. And the concept of death is completely incoherent. And if you run a simulation of someone, it doesn't make any difference to anything.
Is that all just so obvious that just no-one bothers mentioning it?
"There's a short program that can run all possible programs, OMG" is a good summary. I'll put it at the top.
comment by asr · 2013-12-13T06:52:03.356Z · LW(p) · GW(p)
There's a much simpler argument that gets the same conclusion.
Suppose we write down the position of every particle in the universe. That's a very big bitstring. But every possible bitstring is contained within N, the set of natural numbers. Therefore, a Turing machine that prints successive integers will also enumerate all possible finite universes.
You can also omit the Turing machine and just say "consider the set N. It includes an encoding of every possible universe."
I don't think this has any very deep significance, though. The only lesson I draw is that the set of all natural numbers includes some large integers that have very high information content.
is there some subtle point here that I'm missing?
Replies from: johnlawrenceaspden↑ comment by johnlawrenceaspden · 2013-12-16T19:25:36.171Z · LW(p) · GW(p)
is there some subtle point here that I'm missing?
I don't think so. You're saying 'Library of Babel' to my 'Simple Process that Computes Everything'. And obviously there's a continuum between them which includes 'a program to print out all the integers'
But I get a much stronger emotional reaction to a computation that's actually being performed than to a record of one having been performed.
It feels like the difference is something to do with swapping space and time is important.
So now I think: What about a 1-d turing-equivalent cellular automaton running that SPCE program? Where every new row appears below the previous row, so that you can look at it either as a flat piece of paper where consciousnesses exist, or as a process in which consciousnesses exist.
But yes, I think the entire content of my post is something like OMGintegerswoo!? And even after admitting that, I still find the idea of these tables mind-blowing in an ontologically-reassuring sort of way.
I think people really care about the distinction between 'results' and 'computation'.