User loginNavigation |
archivesHalting program density?We know the density of primes tends towards 1/log(n) as n get larger. Do we know anything about the density of programs which halt? For example, take your favorite universal turing machine. Generate all programs of size 1. Record the percentage of programs that halt in less than 1 millisecond (or 10,000 head movements, or some other metric). Run the remaining programs for 10 milliseconds each, record the percentage which halt. Continue for 100, 1000, etc. milliseconds. Then repeat the procedure for all programs of length 2,3,4..N. Do we know anything about the surface just described? It surely must be monotonically increasing. Can we say anything more? Can we describe any aspect of it with numbers? This seems like it might be an easier task to undertake, compared to the corresponding question of "What's the density of provable truths in arithmetic?" Thoughts? Reproducing Programs implement Lazy ListsAlong the lines of the quine discussion happening in another thread, Manfred von Thun wrote a new page for the Joy site, Reproducing Programs implement Lazy Lists. This connects nicely with Jeremy Gibbons spigot algorithms paper, one example of which is his IOHCC 2004 submission PiSpigot. By shapr at 2005-03-18 17:08 | Fun | Functional | Implementation | 1 comment | other blogs | 4970 reads
|
Browse archivesActive forum topics |
Recent comments
22 weeks 12 hours ago
22 weeks 16 hours ago
22 weeks 16 hours ago
44 weeks 1 day ago
48 weeks 3 days ago
50 weeks 1 day ago
50 weeks 1 day ago
1 year 4 days ago
1 year 5 weeks ago
1 year 5 weeks ago