User loginNavigation 
Halting 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? By Greg Buchholz at 20050318 16:38  LtU Forum  previous forum topic  next forum topic  other blogs  4826 reads

Browse archivesActive forum topics 
Recent comments
4 days 21 hours ago
5 days 2 hours ago
5 days 19 hours ago
6 days 2 hours ago
6 days 4 hours ago
6 days 9 hours ago
6 days 14 hours ago
6 days 15 hours ago
6 days 18 hours ago
6 days 20 hours ago