OK, I found an example that quite clearly contradicts CT thesis, unless we considerable weaken it (to something weaker than emulability).
The concept is rather simple. We introduce a meta-program that can, additionally to computing what a normal program does, reflect upon the states of program that is doing the "normal" computation. For example, we have universal turing machine that computes something using the states "0" and "1". We can write a meta-program that does the computation that the universal turing machine is doing, but also checks whether the states "A" or "B" has been used during the computation, and if it has been used, it produces an error message. Of course, if we run the program, it will not produce an error message. If we have another universal turing machine that tries to emulate that system, but it uses the states "A" and "B". If it emulates the system, it will either produce an error message (which does not replicate the function of the original program) or it will emulate the program incorrectly, by acting like the states used to do the computation are "0" and "1" (which they aren't, thus the emulation is incorrect). Don't be confused, the meta-program is reflecting on which program is actually doing the computation (which is well defined from its perspective), not which "is doing" the computation in the emulation. It can be argued that it is possible to emulate what the program *would* do if another program was doing the computation. But the task is to emulate the meta-program itself, not the meta-program in another context. So every possible emulation we do using the UTM with states "A" and "B" is counter-factual. It doesn't replicate the function of the meta-program, only the function of the meta-program as it would act in another context. Note that counterfactual emulation can still be used to make sense of the meta-program on some level, but only by using the counterfactual emulation and mentally putting it in the right context. We can use the emulation on the wrong level B (using machine B) to get a result that "would be" correct if the computation was implemented in another manner (on level A / using machine A). If we want to have the correct emulation on that level B, we just need to create another emulation C that is wrong on its level, but is correct on level B, etc... So to actually emulate the meta-program using UTMs we need to create an unbound amount of counterfactual emulations and interpret them correctly (to understand in which way and at which point the "emulation" is correct and in which way it is not). benjayk -- View this message in context: http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34407926.html Sent from the Everything List mailing list archive at Nabble.com. -- You received this message because you are subscribed to the Google Groups "Everything List" group. To post to this group, send email to everything-list@googlegroups.com. To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/everything-list?hl=en.
