Hi Matt
Re Halting/non-halting programs:
This try-out works fine for small values of {program length}. For large values
the problem is essentially unsolvable, though I admit that you could get a fair
feeling for the distribution by simulating a large number of randomly generated
programs. The busy beaver sequence is (provably) the fastest growing number
sequence... (I know because I tried looking for that once but the best I could
come up was with what was apparently called the arrow notation.)
Re NL & pattern finding:
The problem arises with:
- Apples are (the forbidden :) fruit. My laptop is an apple. Therefore my
laptop is (the forbidden) fruit.
- People have legs. Johnny the cripple is a person (a people?). Therefore...
- Eggs are white (or brown:). Yolk is in the egg. Therefore yolk is white.
>>> Matt Mahoney <[EMAIL PROTECTED]> 06/08/07 9:24 PM >>>
What is the shortest C program that does not halt? Here are some 136 bit
programs:
What is the shortest halting program in Java? I can find 2916 programs of
length 360 bits, but nothing shorter, for example:
- Frogs are green. Kermit is a frog. Therefore Kermit is green.
- Cities have tall buildings. New York is a city. Therefore New York has
tall buildings.
- Summers are hot. July is in the summer. Therefore July is hot.
-----
This list is sponsored by AGIRI: http://www.agiri.org/email
To unsubscribe or change your options, please go to:
http://v2.listbox.com/member/?member_id=231415&user_secret=e9e40a7e
