6 Aug 2002 Bram   » (Master)

This diary entry is all mathematical musings

Concreteness

I've been thinking about how to differentiate between amorphous conjectures like the axiom of choice, whose truth values are ambiguous, and the goldbach conjecture, which is clearly either true or false. If it's true but unprovable, one can add an axiom saying that there is a counterexample, and no logical contradiction will result, but this is strictly a bizarre creature of axiom-land. It clearly is not something we wish to accept. I believe that the goldbach conjecture is concrete while the axiom of choice is not.

Any conjecture of the form 'turing machine X halts' is concrete, as is any conjecture which can be shown to be equivalent to such a statement. Some statements I consider to be concrete can't be expressed this way - for example, the twin primes conjecture, so another statement must be included. Specifically, all statements of the form 'turing machine X hits state s an infinite number of times'. Whether this encompasses all statements which I'd like to consider concrete I don't know.

Ludicrously Large Numbers

The second category of concreteness seems fundamentally more powerful than the first one, which leads to an interesting conjecture. Let us define a 'prescient busy beaver' as a turing machine with no halting condition but having a specific blessed state, and it halts after the last time it will ever visit the blessed state. We define pbb(x) for any integer x as the largest number of steps any prescient busy beaver with x states will take before halting (excluding non-halting ones, of course.) I conjecture that for any arbitrarily large integer c, there exists a d such that for all x > d, pbb(x) > bb(x * c).

Less Ludicrously Large Numbers

While on the subject of ridiculously large numbers, I came up with an interesting variant of goodstein's theorem. Goodstein's really operates on ordered pairs (x, y), and every turn x undergoes a transformation involving expressing it in terms of y and changing all the y's to y+1, then subtracting 1, and incrementing the second number by 1. The theorem still applies if we instead replace y with x, which results in the number of steps necessary to inevitably hit 0 going from unimaginably huge to ... yet even more unimaginably huge. This has gotten quite ludicrous, but I still enjoy the game of naming the largest number you can by specifying a turing machine which halts after that number of steps.

I wonder if there are any reasonably expressible processes which can be shown to halt based on transfinite induction using a larger cardinal. Intuitively, I would guess there is, and such a creature would completely toast the example I just gave in terms of time to halting.

Concreteness of Large Cardinals

I believe that the statement of the existence of large cardinals is, in fact, concrete. Clearly they aren't conrete in the strict sense, but their consistency can be shown to be equivalent to statements which I do very strongly feel to be not only concrete, but also true.

For any axiomatic system, we inevitably wish to add an axiom stating that all the other axioms are consistent. We then wish to add an axiom stating that that axiom is consistent, then generalize to another, and another, etc. until we generalize to aleph null. This can be furthur generalized (via statements beyond my own mathematical ability to express properly) to larger infinite numbers, and suddenly the whole cardinal heirarchy appears.

Although this intuitive justification is rarely stated, I believe it's the reason so many mathematicians believe strongly in large cardinal axioms, despite their otherwise very loose justification. Hopefully some day we'll figure out a way of stating within mathematics that the mathematics itself is consistent without falling into the trap laid by Godel, and then the cardinal heirarchy will be derivable in a coherent manner, instead of on an ad hoc intuitive basis.

Latest blog entries     Older blog entries

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!