Is the universe a tautology? (Explanation inside)

"hey, it's going to be there somewhere"

Only if it exists. Ha!

Oh, but it does! There's only |Z| Turing machines, and they all either halt or don't.

...Except you're still relying on the consistency of ZFC, and you can't get around that without breaking Godel's Theorem.

Only if it exists. Ha!

It is possible to prove that it exists, actually (the argument is the one Yej wrote), but you need the law of the excluded middle for that. So you can do that in the framework of classical mathematics, but not — for example — if you reject mathematical platonism and subscribe to Intuitionism instead.

Which is a very elegant philosophy of mathematics, under many points of view, but leads to many surprising consequences — for example, it implies that all our construction with bigger and bigger infinities makes no sense, and that pi (3.14 and so on) does not really exist either

I could go on a little more about this topic, but perhaps I am being boring — tell me if you are interested, and I can try to discuss a little the main philosophies of mathematics and their consequences for this kind of problem.

edited 25th May '11 5:49:33 AM by Carciofus

Actually I checked again, and there aren't |Z| Turing machines; there's 2^|Z|. That means your real numbered books aren't guaranteed to have all the results.

Yes, by all means I want to hear more. Especially about Intuitionism, that sounds interesting.

edited 25th May '11 6:04:55 AM by Sati1984

• A finite, nonempty set of states (including a starting state and an end state);
• A set of transitions, which specify for every non-end state and every letter of the alphabet (0 or 1 in our case) a new state, what should be written on the tape as the new value, and whether to go left or right or stand still.

For the set of states, let us just encode it as the number N of them. Let us also say that 0 is always the initial state, and 1 is always the terminating state . Then every transition is of the form:

(State, Value) -> (State', Value', Direction)

where State and State' are integers less than N, Value and Value' are 0 or 1, and Direction is Left, Right or Stop. Plus we always have a finite number of transitions, because we have finitely many states.

So it seems to me that we can always represent a Turing Machine as a finite string: just to make an example, the one that goes "keep going right in the tape until you meet a 1, then erase it and stop" is encoded like

2
(0, 0) -> (0, 0, Right)
(0, 1) -> (1, 0, Stop)

Now if we can encode all Turing machine as finite ASCII strings, we can just take the bytecode and treat it as one huge binary number, and we are done. So, unless I made some mistake somewhere, |Z| Turing machines should be enough.

However, I also specified that I want the answer for all inputs. If I am ok with having only finite inputs — let's say, inputs which only a finite number of ones in the tape — then there is no problem, I can put the description as a finite string inside the sourcecode of the Turing machine and be done.

If I want infinite inputs too, then you are definitely right, I need bigger books

OK, this evening I'll try to write down something — sorry for the delay, but I'd better check a few things just to be sure I am not writing nonsense

edited 25th May '11 6:32:59 AM by Carciofus

I think the key is the transition function, which has signature of Z x Z -> Z x Z x {L,R}. I do not think that's equivalent to |Z|, since I can have a set of functions for (1,1) -> (1,1,L) or -> (1,2,L) then -> (1,3,L) etc, and then a totally different set for ->(1,1,R), ->(1,2,R) and so forth. And then have more infinite sets again for each (x,y) tuple.

Except I know that |Z x Z| is actually equivalent to |Z|, so I'm not sure.

(And I think you need all infinite inputs to be able to prove arbitrary theorems.)

edited 25th May '11 6:41:41 AM by Yej

Why are you putting Z in the type the transition function? At least for the definition I seem to remember, you have a finite set of states and a finite vocabulary — you get to specify their size, but they cannot be infinite.

Otherwise, you are absolutely right — the set of functions from Z x Z to Z x Z x {L, R} is definitely not countable (the easy way to check this is to show that real numbers can be encoded by them).

For proving theorems... well, let's say that I want a theorem prover that tells me, given a set of axioms (ZFC, let's say) if something is a consequence of them. This would allow me to solve quite a lot of stuff.

Then I write a Turing Machine that just keeps proving theorems from the ZFC axioms until it meets the statement that I want to prove. This can be done already: of course, the problem is that most interesting theorems would take ages to prove in this way, and that — most importantly — if something is not a theorem this algorithm will just keep trying to prove it forever.

I don't need infinite input strings to do this — I need an infinite work tape, of course, but as I said I can leave these technical details to the engineers .

But now let's say that I know the solution of the Halting Problem for this machine. Then I am done! If it eventually halts, it means that it eventually finds a solution, and hence that the theorem is true; and if it doesn't, then no proof exists, and therefore the theorem does not hold.

So I prime the machine with, let's say, the Caratheodory Conjecture and I get a shiny Fields Medal to put on my fireplace.

You're states and vocabulary are finite yes, but we're interested in the size of all possible machines, which has Z different vocabuluries/states.

Also, you're plan to take over the world field of mathematics is stumped for another reason: The Library contains all the wrong results too.

edited 25th May '11 7:00:02 AM by Yej

But then there are not Z states/symbols. They are n, for some fixed (but arbitrary) integer n.*

There is a difference here. The union, for all n, of the set of all functions from {1..n} to {1..n} is infinite, but countable; however, as said, the set of all functions from Z to Z is uncountable.

The same holds for the transition functions: the union, for all n, of*

{1..n} x {1..n} -> {1..n} x {1..n} x {L, R}

is countable, even though Z x Z -> Z x Z x {L, R} is not.

But yes, unless the Library contains a helpful Librarian I am quite stumped here

edited 25th May '11 7:23:36 AM by Carciofus

"unless the Library contains a helpful Librarian I am quite stumped here"

You just gave me a webcomic idea. I can't draw it since I can't draw, but I will describe it here (imagine it in the style of XKCD):

• Panel 1: Stickfigure stands in front of a building, the caption above the entrance says New York Public Library. Thought bubble above the head figure's head: “Ah, a huge library! I bet they think they have everything..."

• Panel 2: The figure walks up the stairs towards the entrance. No text.

• Panel 3: Pictured: The librarian's desk with the sitting librarian on the right, the main character on the left, standing. Text bubble for the main character: “Do you have The Flight of the Piano-Man by Richard Thomas Berthold?” Librarian: “Let me check...

• Panel 4: Picture is the same. The librarian asks: “What was the last name of the author again?” Main character: “Umm... Berthold”.

• Panel 5: Picture is the same. Librarian: “Unfortunately, it seems that we don’t have this book. I’m sorry, it’s very rare that we don’t have something…” Main character: “It’s a very important book for me, so I will not be a member of this library, if you don’t have it...”

• Panel 6: Cut to outside, the main character is descending on the stairs. On a separated part of the panel in the upper left corner, there is some text: “My favorite passttime: Going into a huge library where they think they have everything, and asking for a randomly made-up-on-the-spot book. And watch their faces.”

• Panel 7: The main character arrives in front of another building, but we can't see the area above the entrance, just the steps and the door. Thought bubble above the head of the main character: “This library looks huge too!“

• Panel 8. Main character is in the process of going up on the stairs. Thought bubble: “I just love doing this!”. But now, due to the elevated POV, we see the caption above the entrance : The Library of Babel.

I don't think I understand the sense of the word "tautology" as used in the OP (and by Borges apparently). A tautology is a statement that is never false. That seems orthogonal to thing like language or the world. (But, "all series of symbols are understandable in some language, where a language is a function from series of symbols to understandings" could be considered tautologous?)

Technically, a tautology is a statement that is unconditionally true given all of its precepts. "The universe is the universe" is a tautology, but by no means the most complex kind available. "It is that way because I say so," is a rhetorical tautology.

From Wikipedia: "A formula of propositional logic is a tautology if the formula itself is always true regardless of which valuation is used for the propositional variables."

edited 26th May '11 9:31:15 AM by Fighteer

That still seems orthogonal to me. A language isn't a statement.

A language is a framework in which to make statements. Clearly you could create a language in which "true" and "false" are not exclusive logical statements but I'm not sure how you'd get anything useful done in such a language. Language has to make reference to actual, demonstrable things in order to be of any use.

edited 26th May '11 9:38:12 AM by Fighteer

As Carciofus mentioned, intuitionistic logic, which lacks the law of the excluded middle ("P ∨ ¬P") is sometimes used. You can prove less things than you can with classical logic, though.

The principle of explosion means that a language that permits P and not-P permits any sentence whatsoever as "true."

If your logic has the principle of explosion, sure.

Paraconsistent Logics, for example, don't. They are pretty fun (and quite useful for certain AI applications: for example, they are one of the possible approaches to the problem of having to work with possibly inconsistent theories).

As for the promised introduction to Intuitionism: I am lazy, sorry — I will write it up, but I do not want to botch it up too badly. Give me a few days.

EDIT:

edited 26th May '11 10:38:14 AM by Carciofus

From the article linked to in the OP:

So if I understand this correctly, every possible book that could ever be written is here somewhere. But that doesn't imply that they are all correct, no? The universe wouldn't be a tautology unless every book was true. Most of the books are actually gibberish, and even those that make sense may be erroneous. In fact, the number of books that describe things that are true may be a very small minority.

For another thing, Borges doesn't say that the books contain all truths, only that they contain everything that can ever be written, in any conceivable language. There may be a vast number of truths that cannot be expressed in a coherent language (due to limitations of the the human mind and languages). Thus, there may be no "Book of All Books" that contains everything that is true.

That being the case, I dont see a tautology involved.

I don't think there's such a thing as an inexpressive truth, despite the existence of unprovable expressions.

How would you know that?

Depends on what you mean by "describe". For any given anything, there's a language that maps it to meaning "up is the opposite of down" or what have you, so considered simply as strings of characters, every book describes every possible true statement.

oh and by the way

ETA: Of course, in a practical sense, the vast vast majority of all the books are gibberish for any given language, and of those that aren't it's indeed impossible to discern right from wrong without external evidence. The point of the story is how maddeningly useless the library is.

edited 26th May '11 12:25:15 PM by Tzetze

So, therefore, the answer to the OP is "No."

ETA: The library is, in fact, the human imagination unconfined by facts or logic. It is indeed maddening, perhaps literally...

edited 26th May '11 1:45:59 PM by DeMarquis

It's basically a relatively complicated exercise at examining the concept of "pointless".

Let me clear it up a bit what I meant by tautology in the OP.

The principle was that language is a tautology, because the gibberish books can be meaningful in certain languages. So all books are meaningful and meaningless at the same time.

So in Real Life, the book which describes the method of how to levitate, can be true or false. Right now, I think we don't know enough physics to rule out the possibility of such method. So even if the books don't warp reality, there still could be many books that describe applicable Real Life phenomena we haven't discovered yet. Right now we can't decide what's reality and what is not. Anything could be real. If we interpret the universe from a different POV, the laws of nature as we see them now, fall apart. When you look at a statement, you can always find a POV in which it is true.

If we assume that science itself is a mental construct and laws that we accept as laws of nature are arbitrary laws too, designed by some scientists. They have been tested, but not in all possible scenarios/situations. For any given law we accept, there is a possibility to construct and environment in which it doesn't work...

This was my trail of thought anyways.