Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Handwaving here, but I think longest running machines can't follow a specific structure in general.

Rough sketch of an argument:

Let's construct a number from all intermediate states of the machine concatenated. The number of digits of this number should correspond to the runtime (sketchy). We only care about the halting machines, so it's finite. We know that it must be unique because if a smaller machine computes the same number, we could get a bigger number by simply running the smaller program and doing other nonsense. That means the biggest programs are komolgorov optimal, and the numbers themselves should be k-trivial and thus nearly but not quite computable. Since they're not computable, the programs themselves can't follow a structure to generate them (since that would be computable in turn for larger values).



Of course, there can't be some grand global structure to describe all the champions in one go. But there could be properties that many have in common, e.g., predominantly consisting some number of nested recursions, characterized by some transfinite ordinal. For instance, this particular machine recurses over the first several hyperoperations.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: