| abz | MarcWeber: joined |
| dino- | glguy: Oh come on now, the bleu-class cheeses are delicious. |
| Saizan | hxt is very nice the moment you realize it's like a list monad with arrow combinators |
| emu | count halting allPrograms / count (not . halting) allPrograms |
| procyon112 | hehe |
| chessguy | lol |
| Saizan | you can calculate the chaitin constant! :D |
| monochrom | I have a code optimiser that simplifies that code to 0. |
| kscaldef | Saizan: I'm not sure I have enough haskell experience for that realization to apply |
| procyon112 | Saizan: Isn't it effectively 1? |
| Heffalump | so, arrows are supposed to be good at tracking static properties of functions, right? |
| emu | count halting allPrograms / length allPrograms, sorry |
| chessguy | it's oo/oo |
| emu | counting and length are probably not good ways to put this |
| Saizan | procyon112, isn't it the probability that a random program halts? and is quite impossible to know its value |
| monochrom | lim n->oo (count programs under n that halts / n) |
| emu | that sounds better |
| action | monochrom was a mathematician |
| monochrom | was a mathematician |
| action | emu is not |
| emu | is not |
| procyon112 | Saizan: The research I've seen estimates the value as infintessimally close to 1. |
| action | monochrom is not |
| monochrom | is not |
| Syzygy- | monochrom: Was? What happened? |
| monochrom | I entered computer science. |
| action | dylan wants a new job |
| dylan | wants a new job |
| procyon112 | Saizan: So, all programs are non-halting, except for the infinitely small subset we are actually interested in ;) |
| emu | that speaks about decidable languages then too? |
| procyon112 | Essentually, 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. |
| Heffalump | dylan: what's wrong with your current one? |
| emu | approaches 1? that would be 1:1 |
| Heffalump | procyon112: is the argument easy to summarise? |
| procyon112 | emu: 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. |
| emu | whacha 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 |
| Saizan | yeah, you generate all bit-strings of lenght < n and see if they halt |
| procyon112 | emu: I haven't personally, but I've seen a few papers that did more or less that for different representations. |
| emu | then you're testing linear bounded automatons |
| procyon112 | emu: 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. |