Print Story A quick mathy diary
Diary
By whazat (Wed Mar 31, 2004 at 09:47:39 PM EST) (all tags)
Where-in I discus some Algorithmic Information theory stuff. And other stuff to do with the halting problem.

Also to settle the house argument, a poll on which is the weirdest food to dislike.



A canonical program is the shortest program that creates a certain series. This  has to do with the Kolmorogov complexity and Chatiin complexity (I haven't quite reconciled their differences yet).

My question is what does distribution of canonical programs look like. Would it be anything like primes? As there should be fewer longer programs that are canonical, but still there are longer series that could be described. That got me on to thinking about the randomness of primes. How random are the digits of primes? I shall have a fiddle around and try and work out the randomness of primes vs non-primes.

This is a bit moot as working out whether a program is canonical is I believe equivalent to the halting problem.

Which brings me onto the next topic. Assuming you have a program X that is canonical that works out whether a program halts or not up to programs of the length of X.

Any program that attempts to embed X in itself would be longer than X and so not create a paradox with regards to halting.

< A Pebble | BBC White season: 'Rivers of Blood' >
A quick mathy diary | 13 comments (13 topical, 0 hidden)
Is it the food or the dislike? by Dr H0ffm4n (6.00 / 1) #1 Wed Mar 31, 2004 at 10:47:07 PM EST
Which one do you want to know is weird?

The finite-size halting problem: nope. by i (3.00 / 0) #2 Wed Mar 31, 2004 at 11:36:40 PM EST
See my diary :)


I was thinking of paramaterless programs by whazat (3.00 / 0) #5 Thu Apr 01, 2004 at 02:56:59 AM EST
However as long as you restrict the system of S + M to having a lesser complexity than Pm, the system of logic is not capable of dealing with the Natural numbers and so Godels first theorem doesn't hold.

--
The revolution will not be realised
[ Parent ]
Three cases by Dr H0ffm4n (3.00 / 0) #6 Thu Apr 01, 2004 at 03:40:42 AM EST
  1. Some algorithms are provably canonical.
  2. Some algorithms are provably not canonical.
  3. The rest.

In the case of S not dealing with natural numbers then it cannot even express the halting of M, let alone decide it. So Pm is undefined since it specifies explicitly:

PM checks all theorems in S one by one and halts when it finds one that says "M does (not) halt

[ Parent ]
It can express a subset of natural number by whazat (3.00 / 0) #11 Fri Apr 02, 2004 at 05:33:30 AM EST
Just not all of them. Like most normal computers. Does that affect your reasoning?

--
The revolution will not be realised
[ Parent ]
Let me see by Dr H0ffm4n (5.00 / 1) #12 Fri Apr 02, 2004 at 07:35:12 AM EST
Yes and no. It only applies to series of finite length.

You are effectively replacing the infinite storage of a Turing machine with some fixed finite storage. X must have enough storage to enumerate all possible states  of any program it is trying to decide the halting question for (e.g. PM is trying to decide whether M halts in i's example). That is a power relation and hence the storage of PM must be be at least 2the storage of M.

[ Parent ]
Mmm... by i (3.00 / 0) #8 Thu Apr 01, 2004 at 05:27:17 AM EST
In any S there exist true unprovable statements of the form "M does not halt" (see my one-liner). Take smallest such M. You can't build your canonical machine that can  handle anything bigger than M and prove it correct in S. Because if you could, that would be a proof of "M does not halt" in S.

It doesn't mean that such a machine does not exist. It exists for any size limit L, simply because there's a finite number of distinct functions that can handle input of size L or less. Your machine is one such function. You just can't know which one.


[ Parent ]
No!! by Dr H0ffm4n (3.00 / 0) #9 Thu Apr 01, 2004 at 07:33:41 PM EST
In any S there exist true unprovable statements

This is wrong or at the very least misleading for two reasons:

  1. S has to have certain properties for there to be undecidable statements. Not all axiom systems have undecidable statements.
  2. The statement that the unprovable statements are still true is a heavily platonic interpretation even when S is an arithmetical axiom system. In what sense are they true?


[ Parent ]
There. by i (5.00 / 1) #10 Fri Apr 02, 2004 at 03:13:06 AM EST
  1. We only deal with systems no weaker than integer arithmetics, they all have needed properties. In a weaker system you can't even define a Turing machine.
  2. True means true in our model, which is the lambda calculus or its Turing-style equivalent. Or something. I'm not quite sure myself.



[ Parent ]
I know, just call me Mr Pedant by Dr H0ffm4n (3.00 / 0) #13 Fri Apr 02, 2004 at 07:37:24 AM EST
Pedantry is required in this area IMO. Sloppy phrasing is often copied and quoted and then rephrased again. You end up with a Chinese whispers effect justifying all sorts of crazy ideas.

[ Parent ]
Any form of chocolate by anonimouse (3.00 / 0) #3 Wed Mar 31, 2004 at 11:37:04 PM EST
..because it should hit your pleasure centres in ways too numerous to count, so if you don't like it you must be weird.

Girls come and go but a mortgage is for 25 years -- JtL
Pineapple on savoury. by Breaker (3.00 / 0) #4 Thu Apr 01, 2004 at 02:52:01 AM EST
It's just plain wrong on pizza, no idea what it's doing on gammon and keep it out of my curry if you like your teeth.

That said, the only exception that proves the rule is certain Chinese Sweet and Sour sauces.

I'll happily eat it with ice cream, or in a fruit salad, but the minute it gets cooked it's into uncharted levels of depravity.


You lost me. by eann (3.00 / 0) #7 Thu Apr 01, 2004 at 04:00:30 AM EST

The distribution of canonical programs would look like the distribution of series, whatever that means.  The distribution of lengths of canonical programs is probably what you meant (judging from context).  I think I'd expect a mostly-log-linear Bradford (or Zipf, or Pareto, or Mandelbrot, etc.) pattern, but I don't actually know if primes are Bradfordian.  If I can think of some reason why it might be interesting if they are, then I'll work on that.

But my real sticky point is later:

Assum[e] you have a program X that is canonical that works out whether a program halts or not up to programs of the length of X.

What does that mean?  If a canonical program is the shortest to produce a series, what's the series?


-------------
I'm not trolling here...just trying to earn my badge in the PC Police Force. —tps12
$email =~ s/0/o/;


A quick mathy diary | 13 comments (13 topical, 0 hidden)