5 ms·
> In theory you can enumerate all Turing machines of a given length, or all Python programs of a given length, and find the shortest one that does a given task,
by Simon_says 8y ago
> In theory you can enumerate all Turing machines of a given length, or all Python programs of a given length, and find the shortest one that does a given task, but the list grows exponentially with length.
That works as long as you solve the halting problem first.
- kryptiskt 8y agoYou don't have to do anything impossible, just something exceedingly impractical. Because we know that the function doesn't halt if its runtime exceeds the busy beaver number for that length. Now, we will obviously not know that for any non-trivial length, but in theory it's fine.
- daveFNbuck 8y ago> Now, we will obviously not know that for any non-trivial length, but in theory it's fine. It's not fine in theory because we can't know the busy beaver number for any Turing machine larger than the one doing the enumeration.
- Simon_says 8y agoYou can't know the busy beaver number without solving the halting problem.
- murbard2 8y agoFor that, you can replace Kolmogorov complexity with Levin complexity, which penalizes the Kolmogorov complexity by adding the log of the execution time. Since sufficiently advanced Turing machines are all equivalent up to a multiplicative factor, Levin complexity is defined up to a constant, as is Kolmogorov complexity.