5 ms·
A Turing Machine is an idealized computer. But no computer/TM can find out which of the possible 61.519 4-state TMs can write the longest string of 1's on a bla
by dhs 18y ago
A Turing Machine is an idealized computer. But no computer/TM can find out which of the possible 61.519 4-state TMs can write the longest string of 1's on a blank tape before halting.
- xlnt 18y agoA computer can try each TM one by one in the same way the humans did. If you're talking about the halting problem now, humans also don't know whether the TM they are manually simulating will halt eventually. And you still haven't said specifically what the thing is that the humans do and computers can't.
- dhs 18y agoNo, a computer cannot do it, due to incompleteness (Once there was a man called Kurt Gödel...) Bringsjords experiment proves that humans can "hypercompute" uncomputable functions. The great majority of functions which exist are uncomputable.