4 ms·
The Busy Beaver is a classic example of a function which is not computable by a Turing Machine.
by dhs 18y ago
The Busy Beaver is a classic example of a function which is not computable by a Turing Machine.
- xlnt 18y agoYou haven't said which step he took to compute it which a turing machine can't do.
- dhs 18y agoThere are many steps. You have a set of different Turing Machines with alphabet {0,1}, each of which has, say, 4 states. You want to know which of these is the one that, starting from a tape filled with 0's, can write the largest number of consecutive 1's onto the tape, before it halts. If it halts - you don't know that in the beginning. A human can find out, by manually simulating the sequence and counting the steps. It's a lot of work - there are 61.519 possible 4-state machines -, but Bringsjord (or more likely, a group of undergrads available to him) has/have done it. A computer can't do it. For details, please read the paper.
- xlnt 18y agoYou're telling me that a computer cannot simulate steps of a turing machine, one at a time? it can't store the current state of the turing machine, and the rules, in memory, and use the rules to get from one state to the next? Are you really saying that a computer with too little memory can't do it, or something like that? because it seems blatantly obvious that a computer can simulate a turing machine.
- dhs 18y agoA 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.