3 ms·
That'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 yo
by gpm 8y ago
That'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.