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

> You can create an enumeration over all Turing machines

Wait, can you?



Yes. Every possible Turing machine can be defined using a finite number of symbols drawn from a finite alphabet. Each string in a finite alphabet corresponds to an integer, so for every possible Turing machine there is a corresponding integer. There are many conventions for assigning an integer to each Turing machine, but the choice of convention does not matter (so long as it is computable) - the point is, since we can enumerate the integers, and any computable subset thereof, we can enumerate all Turing machines.

Note this only applies to standard Turing machines (whether single tape or multi-tape, deterministic or non-deterministic). It does not apply to special types of Turing machines such as oracular Turing machines.




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

Search: