#haskell - Thu 5 Apr 2007 between 03:00 and 18:53

abzMarcWeber: joined
dino-glguy: Oh come on now, the bleu-class cheeses are delicious.
Saizanhxt is very nice the moment you realize it's like a list monad with arrow combinators
emucount halting allPrograms / count (not . halting) allPrograms
Saizanyou can calculate the chaitin constant! :D
monochromI have a code optimiser that simplifies that code to 0.
kscaldefSaizan: I'm not sure I have enough haskell experience for that realization to apply
procyon112Saizan: Isn't it effectively 1?
Heffalumpso, arrows are supposed to be good at tracking static properties of functions, right?
emucount halting allPrograms / length allPrograms, sorry
chessguyit's oo/oo
emucounting and length are probably not good ways to put this
Saizanprocyon112, isn't it the probability that a random program halts? and is quite impossible to know its value
monochromlim n->oo (count programs under n that halts / n)
emuthat sounds better
actionmonochrom was a mathematician
monochromwas a mathematician
actionemu is not
emuis not
procyon112Saizan: The research I've seen estimates the value as infintessimally close to 1.
actionmonochrom is not
monochromis not
Syzygy-monochrom: Was? What happened?
monochromI entered computer science.
actiondylan wants a new job
dylanwants a new job
procyon112Saizan: So, all programs are non-halting, except for the infinitely small subset we are actually interested in ;)
emuthat speaks about decidable languages then too?
procyon112Essentually, if you introduce general recursion into the language, then the the ratio of non-halting programs to halting approaches 1 as the allowable size of the programs approach infinity.
Heffalumpdylan: what's wrong with your current one?
emuapproaches 1? that would be 1:1
Heffalumpprocyon112: is the argument easy to summarise?
procyon112emu: er... sorry. ratio of non-halting to total count.. my bad
Heffalump: I've only seen it done experimentally.. I'm not sure if it's proven.
emuwhacha do, pick a compact representation of a turing machine and simulate n-bit ones ?
*all n-bit ones
for each n
they still need some kind of bound
Saizanyeah, you generate all bit-strings of lenght < n and see if they halt
procyon112emu: I haven't personally, but I've seen a few papers that did more or less that for different representations.
emuthen you're testing linear bounded automatons
procyon112emu: I'm more interested in the practical applications than the proof, so whether the limit is assymptotically 1 or not is less important to me than "it looks like it, so it's pretty close to something like that", since I'm developing large GP trees.

Page: 2 9 16 23 30 37 44 51 58 65 72 79 86 93 100