3 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 FartyMcFarter 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.
Another problem with this strategy is that it generally requires solving the halting problem: you can only know whether a program "does a given task" when you know whether it halts or not.
- gpm 8y agoThat's only true if you care about knowing when you are done enumerating. The definition of enumeration commonly used in computability does not require that you know when you are done enumerating.
- Hendrikto 8y agoHow can you make progress if your first generated program does not halt?
- gpm 8y agoRun things in parallel. The idea behind most enumeration algorithms looks like this: machines = {} next_program = 0 loop forever: machines.insert(new_turing_machine(next_program)) next_program++ for machine in machines: machine.step() if machine.halted(): machines.remove(machine) if machine has output we want: yield machine
- deleted 8y ago[deleted]
- algorias 8y ago> The definition of enumeration commonly used in computability does not require that you know when you are done enumerating. Sorry, but this is a non-sequitur. In order to find (by enumeration) the shortest program producing a certain output, you absolutely do need to know when you're done, and thus you do need to solve the halting problem.
- gpm 8y agoAh, you're right. I was focusing too much on the statement itself and not the context of it.