Re: Why the Church-Turing thesis?
scribe is no more a program, but a program + an oracle, the >> >>> oracle >> >>> > obviously is not simulable on a turing machine, or an infinite >> regress >> >>> of >> >>> > level. >> >>> > >> >>> > >> >>> The simulated hardware can't fail in the model, just like a turing >> >>> machine >> >>> can't fail. Of course in reality it can fail, that is beside the >> point. >> >>> >> >>> You are right, my explanation is not that clear, because it is a quite >> >>> subtle thing. >> >>> >> >>> Maybe I shouldn't have used the word "hardware". The point is just >> that >> >>> we >> >>> can define (meta-)programs that have access to some aspect of programs >> >>> that >> >>> are below it on the program hierarchy (normal programs), that can't be >> >>> accessed by the program themselves. They can't emulated in general, >> >>> because >> >>> sometimes the emulating program will necessarily emulate the wrong >> level >> >>> (because it can't correctly emulate that the meta-program is accessing >> >>> what >> >>> it is *actually* doing on the most fundamental level). >> >>> They still are programs in the most fundamental sense. >> >>> >> >>> They don't require oracles or something else that is hard to actually >> >>> use, >> >>> they just have to know something about the hierarchy and the programs >> >>> involved (which programs or kind of programs are above or below it) >> and >> >>> have >> >>> access to the states of other programs. Both are perfectly >> implementable >> >>> on >> >>> a normal computer. They can even be implemented on a turing machine, >> but >> >>> not >> >>> in general. They can also be simulated on turing machines, just not >> >>> necessarily correctly (the turing machine may incorrectly ignore which >> >>> level >> >>> it is operating on relative to the meta-program). >> >>> >> >> >> >> I still don't see why, what you describe is wishful thinking, or you're >> >> wrong, or you can't explain correctly, what I understand from what you >> >> write, is that you are wrong. >> >> >> >>> >> >>> We can still argue that these aren't programs in every sense but I >> think >> >>> what is executable on a normal computer can be rightfully called >> >>> program. >> >>> >> >> >> >> Then if it's executable, then the simulated thing can't be different >> >> (give >> >> different results) than the non simulated one, so it's clear you don't >> >> understand what is a computer and what is a program. >> >> >> >> >> > And I can show that you're wrong: >> > >> > - You say you can write a program on an actual computer that can know it >> > is >> > running on "real" hardware such that I could not create a virtual >> > machine/interpreter running that program, with the program giving the >> same >> > result. >> > >> That's not what I am saying. I am saying that if it gave the same results, >> it may not be correct anymore relative to the levels we defined the >> meta-level on, because the result would have to change based on what this >> virtual machine is doing (because the meta-program it is supposed to be >> emulating accesses the hardware of that virtual machine). > > > So back to what I said before... your "meta" program is an oracle not > emulable by a turing machine, not a program. It can know exactly on what it > runs. > > And your "program" is not a program, it is a program + an oracle (the > oracle is the blackbox that can know on which level the program is running). > > Nothing new here, and nothing that contradict computationalism. > > Quentin > And so as such, contrary to what you claim... such a program *can't* run on actual hardware, because it is *impossible* to implement the oracle it uses. Quentin > > >> Note "may", it >> depends on the specific definitions of levels. >> >> Also, I am not saying that we cannot emulate that program at all, just not >> with a turing machine. That is because we can write a meta-program that >> knows what a turing machine is and knows if one attempts to emulate it and >> subsequently accesess its states to reflect on what it's doing (thus >> making >> the emulation incorrect because it emulates the wrong level). This is not >> necessarily precisely possible in real life, because here no turing >> machines >> exists and there is no clear lowest level. But there being no real >> meta-programs is no more a problem than no real turing machines existing. >> The point is that we can easily define a meta-program that accesses the >> programs that attempt to emulate it, because in theory it is definable >> which >> the lowest level is (simply the level we formulate the computation on). >> That's all that is required to make the point from a computer science >> view. >> You may still say that this is not a program anymore, but I believe that >> it >> fits very well into our intuitive notion of "program". >> >> I would like to see a definition of a program that excludes what I am >> talking about. Do you have one? >> >> benjayk >> -- >> View this message in context: >> http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34424939.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. >> >> > > > -- > All those moments will be lost in time, like tears in rain. > -- All those moments will be lost in time, like tears in rain. -- 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.
Re: Why the Church-Turing thesis?
#x27;hardware'". We can define a (meta-)programs > that > >>> >>> have > >>> >>> >> >> access > >>> >>> >> >> >> to > >>> >>> >> >> >> their "hardware" in the sense of knowing what they are > >>> running > >>> >>> on > >>> >>> >> >> >> relative > >>> >>> >> >> >> to some notion of "hardware". They cannot be emulated > using > >>> >>> >> universal > >>> >>> >> >> >> turing > >>> >>> >> >> >> machines > >>> >>> >> >> > > >>> >>> >> >> > > >>> >>> >> >> > Then it's not a program if it can't run on a universal > >>> turing > >>> >>> >> machine. > >>> >>> >> >> > > >>> >>> >> >> The funny thing is, it *can* run on a universal turing > >>> machine. > >>> >>> Just > >>> >>> >> that > >>> >>> >> >> it > >>> >>> >> >> may lose relative correctness if we do that. > >>> >>> >> > > >>> >>> >> > > >>> >>> >> > Then you must be wrong... I don't understand your point. If > >>> it's > >>> a > >>> >>> >> program > >>> >>> >> > it has access to the "outside" through IO, hence it is > >>> impossible > >>> >>> for a > >>> >>> >> > program to differentiate "real" outside from simulated > >>> outside... > >>> >>> It's > >>> >>> >> a > >>> >>> >> > simple fact, so either you're wrong or what you're describing > >>> is > >>> >>> not > >>> >>> a > >>> >>> >> > program, not an algorithm and not a computation. > >>> >>> >> OK, it depends on what you mean by "program". If you presume > that > >>> a > >>> >>> >> program > >>> >>> >> can't access its "hardware", > >>> >>> > > >>> >>> > > >>> >>> > I *do not presume it*... it's a *fact*. > >>> >>> > > >>> >>> > > >>> >>> Well, I presented a model of a program that can do that (on some > >>> level, > >>> >>> not > >>> >>> on the level of physical hardware), and is a program in the most > >>> >>> fundamental > >>> >>> way (doing step-by-step execution of instructions). > >>> >>> All you need is a program hierarchy where some programs have access > >>> to > >>> >>> programs that are below them in the hierarchy (which are the > >>> "hardware" > >>> >>> though not the *hardware*). > >>> >>> > >>> >> > >>> >> What's your point ? How the simulated hardware would fail ? It's > >>> >> impossible, so until you're clearer (your point is totally fuzzy), I > >>> >> stick > >>> >> to "you must be wrong". > >>> >> > >>> > > >>> > So either you assume some kind of "oracle" device, in this case, the > >>> thing > >>> > you describe is no more a program, but a program + an oracle, the > >>> oracle > >>> > obviously is not simulable on a turing machine, or an infinite > regress > >>> of > >>> > level. > >>> > > >>> > > >>> The simulated hardware can't fail in the model, just like a turing > >>> machine > >>> can't fail. Of course in reality it can fail, that is beside the point. > >>> > >>> You are right, my explanation is not that clear, because it is a quite > >>> subtle thing. > >>> > >>> Maybe I shouldn't have used the word "hardware". The point is just that >
Re: Why the Church-Turing thesis?
of "hardware". They cannot be emulated using >>> >>> >> universal >>> >>> >> >> >> turing >>> >>> >> >> >> machines >>> >>> >> >> > >>> >>> >> >> > >>> >>> >> >> > Then it's not a program if it can't run on a universal >>> turing >>> >>> >> machine. >>> >>> >> >> > >>> >>> >> >> The funny thing is, it *can* run on a universal turing >>> machine. >>> >>> Just >>> >>> >> that >>> >>> >> >> it >>> >>> >> >> may lose relative correctness if we do that. >>> >>> >> > >>> >>> >> > >>> >>> >> > Then you must be wrong... I don't understand your point. If >>> it's >>> a >>> >>> >> program >>> >>> >> > it has access to the "outside" through IO, hence it is >>> impossible >>> >>> for a >>> >>> >> > program to differentiate "real" outside from simulated >>> outside... >>> >>> It's >>> >>> >> a >>> >>> >> > simple fact, so either you're wrong or what you're describing >>> is >>> >>> not >>> >>> a >>> >>> >> > program, not an algorithm and not a computation. >>> >>> >> OK, it depends on what you mean by "program". If you presume that >>> a >>> >>> >> program >>> >>> >> can't access its "hardware", >>> >>> > >>> >>> > >>> >>> > I *do not presume it*... it's a *fact*. >>> >>> > >>> >>> > >>> >>> Well, I presented a model of a program that can do that (on some >>> level, >>> >>> not >>> >>> on the level of physical hardware), and is a program in the most >>> >>> fundamental >>> >>> way (doing step-by-step execution of instructions). >>> >>> All you need is a program hierarchy where some programs have access >>> to >>> >>> programs that are below them in the hierarchy (which are the >>> "hardware" >>> >>> though not the *hardware*). >>> >>> >>> >> >>> >> What's your point ? How the simulated hardware would fail ? It's >>> >> impossible, so until you're clearer (your point is totally fuzzy), I >>> >> stick >>> >> to "you must be wrong". >>> >> >>> > >>> > So either you assume some kind of "oracle" device, in this case, the >>> thing >>> > you describe is no more a program, but a program + an oracle, the >>> oracle >>> > obviously is not simulable on a turing machine, or an infinite regress >>> of >>> > level. >>> > >>> > >>> The simulated hardware can't fail in the model, just like a turing >>> machine >>> can't fail. Of course in reality it can fail, that is beside the point. >>> >>> You are right, my explanation is not that clear, because it is a quite >>> subtle thing. >>> >>> Maybe I shouldn't have used the word "hardware". The point is just that >>> we >>> can define (meta-)programs that have access to some aspect of programs >>> that >>> are below it on the program hierarchy (normal programs), that can't be >>> accessed by the program themselves. They can't emulated in general, >>> because >>> sometimes the emulating program will necessarily emulate the wrong level >>> (because it can't correctly emulate that the meta-program is accessing >>> what >>> it is *actually* doing on the most fundamental level). >>> They still are programs in the most fundamental sense. >>> >>> They don't require oracles or something else that is hard to actually >>> use, >>> they just have to know something about the hierarchy and the programs >>> involved (which programs or kind of programs are above or below it) and >>> have >>> access to the states of other programs. Both are perfectly implementable >>> on >>> a normal computer. They can even be implemented on a turing machine, but >>> not >>> in general. They can also be simulated on turing machines, just not >>> necessarily correctly (the turing machine may incorrectly ignore which >>> level >>> it is operating on relative to the meta-program). >>> >> >> I still don't see why, what you describe is wishful thinking, or you're >> wrong, or you can't explain correctly, what I understand from what you >> write, is that you are wrong. >> >>> >>> We can still argue that these aren't programs in every sense but I think >>> what is executable on a normal computer can be rightfully called >>> program. >>> >> >> Then if it's executable, then the simulated thing can't be different >> (give >> different results) than the non simulated one, so it's clear you don't >> understand what is a computer and what is a program. >> >> > And I can show that you're wrong: > > - You say you can write a program on an actual computer that can know it > is > running on "real" hardware such that I could not create a virtual > machine/interpreter running that program, with the program giving the same > result. > That's not what I am saying. I am saying that if it gave the same results, it may not be correct anymore relative to the levels we defined the meta-level on, because the result would have to change based on what this virtual machine is doing (because the meta-program it is supposed to be emulating accesses the hardware of that virtual machine). Note "may", it depends on the specific definitions of levels. Also, I am not saying that we cannot emulate that program at all, just not with a turing machine. That is because we can write a meta-program that knows what a turing machine is and knows if one attempts to emulate it and subsequently accesess its states to reflect on what it's doing (thus making the emulation incorrect because it emulates the wrong level). This is not necessarily precisely possible in real life, because here no turing machines exists and there is no clear lowest level. But there being no real meta-programs is no more a problem than no real turing machines existing. The point is that we can easily define a meta-program that accesses the programs that attempt to emulate it, because in theory it is definable which the lowest level is (simply the level we formulate the computation on). That's all that is required to make the point from a computer science view. You may still say that this is not a program anymore, but I believe that it fits very well into our intuitive notion of "program". I would like to see a definition of a program that excludes what I am talking about. Do you have one? benjayk -- View this message in context: http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34424939.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.
Re: Why the Church-Turing thesis?
these aren't programs in every sense but I think what is executable on a normal computer can be rightfully called program. If by normal you mean "physical", then you give a reason to say "No" to the doctor. In that case there is no more any substitution level. Bruno benayk -- View this message in context: http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34423089.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 . http://iridia.ulb.ac.be/~marchal/ -- 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.
Re: Why the Church-Turing thesis?
;>> >> >> > >> >>> >> >> The funny thing is, it *can* run on a universal turing machine. >> >>> Just >> >>> >> that >> >>> >> >> it >> >>> >> >> may lose relative correctness if we do that. >> >>> >> > >> >>> >> > >> >>> >> > Then you must be wrong... I don't understand your point. If it's >> a >> >>> >> program >> >>> >> > it has access to the "outside" through IO, hence it is impossible >> >>> for a >> >>> >> > program to differentiate "real" outside from simulated outside... >> >>> It's >> >>> >> a >> >>> >> > simple fact, so either you're wrong or what you're describing is >> >>> not >> >>> a >> >>> >> > program, not an algorithm and not a computation. >> >>> >> OK, it depends on what you mean by "program". If you presume that a >> >>> >> program >> >>> >> can't access its "hardware", >> >>> > >> >>> > >> >>> > I *do not presume it*... it's a *fact*. >> >>> > >> >>> > >> >>> Well, I presented a model of a program that can do that (on some >> level, >> >>> not >> >>> on the level of physical hardware), and is a program in the most >> >>> fundamental >> >>> way (doing step-by-step execution of instructions). >> >>> All you need is a program hierarchy where some programs have access to >> >>> programs that are below them in the hierarchy (which are the >> "hardware" >> >>> though not the *hardware*). >> >>> >> >> >> >> What's your point ? How the simulated hardware would fail ? It's >> >> impossible, so until you're clearer (your point is totally fuzzy), I >> >> stick >> >> to "you must be wrong". >> >> >> > >> > So either you assume some kind of "oracle" device, in this case, the >> thing >> > you describe is no more a program, but a program + an oracle, the oracle >> > obviously is not simulable on a turing machine, or an infinite regress >> of >> > level. >> > >> > >> The simulated hardware can't fail in the model, just like a turing machine >> can't fail. Of course in reality it can fail, that is beside the point. >> >> You are right, my explanation is not that clear, because it is a quite >> subtle thing. >> >> Maybe I shouldn't have used the word "hardware". The point is just that we >> can define (meta-)programs that have access to some aspect of programs >> that >> are below it on the program hierarchy (normal programs), that can't be >> accessed by the program themselves. They can't emulated in general, >> because >> sometimes the emulating program will necessarily emulate the wrong level >> (because it can't correctly emulate that the meta-program is accessing >> what >> it is *actually* doing on the most fundamental level). >> They still are programs in the most fundamental sense. >> >> They don't require oracles or something else that is hard to actually use, >> they just have to know something about the hierarchy and the programs >> involved (which programs or kind of programs are above or below it) and >> have >> access to the states of other programs. Both are perfectly implementable >> on >> a normal computer. They can even be implemented on a turing machine, but >> not >> in general. They can also be simulated on turing machines, just not >> necessarily correctly (the turing machine may incorrectly ignore which >> level >> it is operating on relative to the meta-program). >> > > I still don't see why, what you describe is wishful thinking, or you're > wrong, or you can't explain correctly, what I understand from what you > write, is that you are wrong. > >> >> We can still argue that these aren't programs in every sense but I think >> what is executable on a normal computer can be rightfully called program. >> > > Then if it's executable, then the simulated thing can't be different (give > different results) than the non simulated one, so it's clear you don't > understand what is a computer and what is a program. > > And I can show that you're wrong: - You say you can write a program on an actual computer that can know it is running on "real" hardware such that I could not create a virtual machine/interpreter running that program, with the program giving the same result. - A program can only interact through IO with the hardware (means it only interact with memory place). - I can replicate *exactly* all the IO the "real" computer would give (including timing, because same thing, external time is an IO) so the claim that you could write a program that could tell apart the real hardware and the VM is refuted, your program running inside the VM would yield the exact same result as if it was running on the real computer. ==> QED > Quentin > >> >> benayk >> -- >> View this message in context: >> http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34423089.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. >> >> > > > -- > All those moments will be lost in time, like tears in rain. > -- All those moments will be lost in time, like tears in rain. -- 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.
Re: Why the Church-Turing thesis?
7;t understand your point. If it's a > >>> >> program > >>> >> > it has access to the "outside" through IO, hence it is impossible > >>> for a > >>> >> > program to differentiate "real" outside from simulated outside... > >>> It's > >>> >> a > >>> >> > simple fact, so either you're wrong or what you're describing is > >>> not > >>> a > >>> >> > program, not an algorithm and not a computation. > >>> >> OK, it depends on what you mean by "program". If you presume that a > >>> >> program > >>> >> can't access its "hardware", > >>> > > >>> > > >>> > I *do not presume it*... it's a *fact*. > >>> > > >>> > > >>> Well, I presented a model of a program that can do that (on some level, > >>> not > >>> on the level of physical hardware), and is a program in the most > >>> fundamental > >>> way (doing step-by-step execution of instructions). > >>> All you need is a program hierarchy where some programs have access to > >>> programs that are below them in the hierarchy (which are the "hardware" > >>> though not the *hardware*). > >>> > >> > >> What's your point ? How the simulated hardware would fail ? It's > >> impossible, so until you're clearer (your point is totally fuzzy), I > >> stick > >> to "you must be wrong". > >> > > > > So either you assume some kind of "oracle" device, in this case, the > thing > > you describe is no more a program, but a program + an oracle, the oracle > > obviously is not simulable on a turing machine, or an infinite regress of > > level. > > > > > The simulated hardware can't fail in the model, just like a turing machine > can't fail. Of course in reality it can fail, that is beside the point. > > You are right, my explanation is not that clear, because it is a quite > subtle thing. > > Maybe I shouldn't have used the word "hardware". The point is just that we > can define (meta-)programs that have access to some aspect of programs that > are below it on the program hierarchy (normal programs), that can't be > accessed by the program themselves. They can't emulated in general, because > sometimes the emulating program will necessarily emulate the wrong level > (because it can't correctly emulate that the meta-program is accessing what > it is *actually* doing on the most fundamental level). > They still are programs in the most fundamental sense. > > They don't require oracles or something else that is hard to actually use, > they just have to know something about the hierarchy and the programs > involved (which programs or kind of programs are above or below it) and > have > access to the states of other programs. Both are perfectly implementable on > a normal computer. They can even be implemented on a turing machine, but > not > in general. They can also be simulated on turing machines, just not > necessarily correctly (the turing machine may incorrectly ignore which > level > it is operating on relative to the meta-program). > I still don't see why, what you describe is wishful thinking, or you're wrong, or you can't explain correctly, what I understand from what you write, is that you are wrong. > > We can still argue that these aren't programs in every sense but I think > what is executable on a normal computer can be rightfully called program. > Then if it's executable, then the simulated thing can't be different (give different results) than the non simulated one, so it's clear you don't understand what is a computer and what is a program. Quentin > > benayk > -- > View this message in context: > http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34423089.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. > > -- All those moments will be lost in time, like tears in rain. -- 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.
Re: Why the Church-Turing thesis?
, not an algorithm and not a computation. >>> >> OK, it depends on what you mean by "program". If you presume that a >>> >> program >>> >> can't access its "hardware", >>> > >>> > >>> > I *do not presume it*... it's a *fact*. >>> > >>> > >>> Well, I presented a model of a program that can do that (on some level, >>> not >>> on the level of physical hardware), and is a program in the most >>> fundamental >>> way (doing step-by-step execution of instructions). >>> All you need is a program hierarchy where some programs have access to >>> programs that are below them in the hierarchy (which are the "hardware" >>> though not the *hardware*). >>> >> >> What's your point ? How the simulated hardware would fail ? It's >> impossible, so until you're clearer (your point is totally fuzzy), I >> stick >> to "you must be wrong". >> > > So either you assume some kind of "oracle" device, in this case, the thing > you describe is no more a program, but a program + an oracle, the oracle > obviously is not simulable on a turing machine, or an infinite regress of > level. > > The simulated hardware can't fail in the model, just like a turing machine can't fail. Of course in reality it can fail, that is beside the point. You are right, my explanation is not that clear, because it is a quite subtle thing. Maybe I shouldn't have used the word "hardware". The point is just that we can define (meta-)programs that have access to some aspect of programs that are below it on the program hierarchy (normal programs), that can't be accessed by the program themselves. They can't emulated in general, because sometimes the emulating program will necessarily emulate the wrong level (because it can't correctly emulate that the meta-program is accessing what it is *actually* doing on the most fundamental level). They still are programs in the most fundamental sense. They don't require oracles or something else that is hard to actually use, they just have to know something about the hierarchy and the programs involved (which programs or kind of programs are above or below it) and have access to the states of other programs. Both are perfectly implementable on a normal computer. They can even be implemented on a turing machine, but not in general. They can also be simulated on turing machines, just not necessarily correctly (the turing machine may incorrectly ignore which level it is operating on relative to the meta-program). We can still argue that these aren't programs in every sense but I think what is executable on a normal computer can be rightfully called program. benayk -- View this message in context: http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34423089.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.
Re: Why the Church-Turing thesis?
2012/9/11 Quentin Anciaux > > > 2012/9/11 benjayk > >> >> >> Quentin Anciaux-2 wrote: >> > >> > 2012/9/11 benjayk >> > >> >> >> >> >> >> Quentin Anciaux-2 wrote: >> >> > >> >> > 2012/9/11 benjayk >> >> > >> >> >> >> >> >> >> >> >> Quentin Anciaux-2 wrote: >> >> >> > >> >> >> > 2012/9/10 benjayk >> >> >> > >> >> >> >> >> >> >> >> >> >> >> >> > > No program can determine its hardware. This is a consequence >> >> of >> >> >> the >> >> >> >> > > Church >> >> >> >> > > Turing thesis. The particular machine at the lowest level >> has >> >> no >> >> >> >> > bearing >> >> >> >> > > (from the program's perspective). >> >> >> >> > If that is true, we can show that CT must be false, because we >> >> *can* >> >> >> >> > define >> >> >> >> > a "meta-program" that has access to (part of) its own hardware >> >> >> (which >> >> >> >> > still >> >> >> >> > is intuitively computable - we can even implement it on a >> >> computer). >> >> >> >> > >> >> >> >> >> >> >> >> It's false, the program *can't* know that the hardware it has >> >> access >> >> >> to >> >> >> >> is >> >> >> >> the *real* hardware and not a simulated hardware. The program has >> >> only >> >> >> >> access to hardware through IO, and it can't tell (as never ever) >> >> from >> >> >> >> that >> >> >> >> interface if what's outside is the *real* outside or simulated >> >> >> outside. >> >> >> >> <\quote> >> >> >> >> Yes that is true. If anything it is true because the hardware is >> >> not >> >> >> even >> >> >> >> clearly determined at the base level (quantum uncertainty). >> >> >> >> I should have expressed myself more accurately and written " >> >> >> "hardware" >> >> >> " >> >> >> >> or >> >> >> >> "relative 'hardware'". We can define a (meta-)programs that have >> >> >> access >> >> >> >> to >> >> >> >> their "hardware" in the sense of knowing what they are running on >> >> >> >> relative >> >> >> >> to some notion of "hardware". They cannot be emulated using >> >> universal >> >> >> >> turing >> >> >> >> machines >> >> >> > >> >> >> > >> >> >> > Then it's not a program if it can't run on a universal turing >> >> machine. >> >> >> > >> >> >> The funny thing is, it *can* run on a universal turing machine. Just >> >> that >> >> >> it >> >> >> may lose relative correctness if we do that. >> >> > >> >> > >> >> > Then you must be wrong... I don't understand your point. If it's a >> >> program >> >> > it has access to the "outside" through IO, hence it is impossible >> for a >> >> > program to differentiate "real" outside from simulated outside... >> It's >> >> a >> >> > simple fact, so either you're wrong or what you're describing is not >> a >> >> > program, not an algorithm and not a computation. >> >> OK, it depends on what you mean by "program". If you presume that a >> >> program >> >> can't access its "hardware", >> > >> > >> > I *do not presume it*... it's a *fact*. >> > >> > >> Well, I presented a model of a program that can do that (on some level, >> not >> on the level of physical hardware), and is a program in the most >> fundamental >> way (
Re: Why the Church-Turing thesis?
2012/9/11 benjayk > > > Quentin Anciaux-2 wrote: > > > > 2012/9/11 benjayk > > > >> > >> > >> Quentin Anciaux-2 wrote: > >> > > >> > 2012/9/11 benjayk > >> > > >> >> > >> >> > >> >> Quentin Anciaux-2 wrote: > >> >> > > >> >> > 2012/9/10 benjayk > >> >> > > >> >> >> > >> >> >> > >> >> >> > > No program can determine its hardware. This is a consequence > >> of > >> >> the > >> >> >> > > Church > >> >> >> > > Turing thesis. The particular machine at the lowest level has > >> no > >> >> >> > bearing > >> >> >> > > (from the program's perspective). > >> >> >> > If that is true, we can show that CT must be false, because we > >> *can* > >> >> >> > define > >> >> >> > a "meta-program" that has access to (part of) its own hardware > >> >> (which > >> >> >> > still > >> >> >> > is intuitively computable - we can even implement it on a > >> computer). > >> >> >> > > >> >> >> > >> >> >> It's false, the program *can't* know that the hardware it has > >> access > >> >> to > >> >> >> is > >> >> >> the *real* hardware and not a simulated hardware. The program has > >> only > >> >> >> access to hardware through IO, and it can't tell (as never ever) > >> from > >> >> >> that > >> >> >> interface if what's outside is the *real* outside or simulated > >> >> outside. > >> >> >> <\quote> > >> >> >> Yes that is true. If anything it is true because the hardware is > >> not > >> >> even > >> >> >> clearly determined at the base level (quantum uncertainty). > >> >> >> I should have expressed myself more accurately and written " > >> >> "hardware" > >> >> " > >> >> >> or > >> >> >> "relative 'hardware'". We can define a (meta-)programs that have > >> >> access > >> >> >> to > >> >> >> their "hardware" in the sense of knowing what they are running on > >> >> >> relative > >> >> >> to some notion of "hardware". They cannot be emulated using > >> universal > >> >> >> turing > >> >> >> machines > >> >> > > >> >> > > >> >> > Then it's not a program if it can't run on a universal turing > >> machine. > >> >> > > >> >> The funny thing is, it *can* run on a universal turing machine. Just > >> that > >> >> it > >> >> may lose relative correctness if we do that. > >> > > >> > > >> > Then you must be wrong... I don't understand your point. If it's a > >> program > >> > it has access to the "outside" through IO, hence it is impossible for > a > >> > program to differentiate "real" outside from simulated outside... It's > >> a > >> > simple fact, so either you're wrong or what you're describing is not a > >> > program, not an algorithm and not a computation. > >> OK, it depends on what you mean by "program". If you presume that a > >> program > >> can't access its "hardware", > > > > > > I *do not presume it*... it's a *fact*. > > > > > Well, I presented a model of a program that can do that (on some level, not > on the level of physical hardware), and is a program in the most > fundamental > way (doing step-by-step execution of instructions). > All you need is a program hierarchy where some programs have access to > programs that are below them in the hierarchy (which are the "hardware" > though not the *hardware*). > What's your point ? How the simulated hardware would fail ? It's impossible, so until you're clearer (your point is totally fuzzy), I stick to "you must be wrong". > > So apparently it is not so much a fact about programs in a common sense > way, > but about a narrow conception of what programs can be. > > benjayk > -- > View this message in context: > http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34417762.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. > > -- All those moments will be lost in time, like tears in rain. -- 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.
Re: Why the Church-Turing thesis?
Quentin Anciaux-2 wrote: > > 2012/9/11 benjayk > >> >> >> Quentin Anciaux-2 wrote: >> > >> > 2012/9/11 benjayk >> > >> >> >> >> >> >> Quentin Anciaux-2 wrote: >> >> > >> >> > 2012/9/10 benjayk >> >> > >> >> >> >> >> >> >> >> >> > > No program can determine its hardware. This is a consequence >> of >> >> the >> >> >> > > Church >> >> >> > > Turing thesis. The particular machine at the lowest level has >> no >> >> >> > bearing >> >> >> > > (from the program's perspective). >> >> >> > If that is true, we can show that CT must be false, because we >> *can* >> >> >> > define >> >> >> > a "meta-program" that has access to (part of) its own hardware >> >> (which >> >> >> > still >> >> >> > is intuitively computable - we can even implement it on a >> computer). >> >> >> > >> >> >> >> >> >> It's false, the program *can't* know that the hardware it has >> access >> >> to >> >> >> is >> >> >> the *real* hardware and not a simulated hardware. The program has >> only >> >> >> access to hardware through IO, and it can't tell (as never ever) >> from >> >> >> that >> >> >> interface if what's outside is the *real* outside or simulated >> >> outside. >> >> >> <\quote> >> >> >> Yes that is true. If anything it is true because the hardware is >> not >> >> even >> >> >> clearly determined at the base level (quantum uncertainty). >> >> >> I should have expressed myself more accurately and written " >> >> "hardware" >> >> " >> >> >> or >> >> >> "relative 'hardware'". We can define a (meta-)programs that have >> >> access >> >> >> to >> >> >> their "hardware" in the sense of knowing what they are running on >> >> >> relative >> >> >> to some notion of "hardware". They cannot be emulated using >> universal >> >> >> turing >> >> >> machines >> >> > >> >> > >> >> > Then it's not a program if it can't run on a universal turing >> machine. >> >> > >> >> The funny thing is, it *can* run on a universal turing machine. Just >> that >> >> it >> >> may lose relative correctness if we do that. >> > >> > >> > Then you must be wrong... I don't understand your point. If it's a >> program >> > it has access to the "outside" through IO, hence it is impossible for a >> > program to differentiate "real" outside from simulated outside... It's >> a >> > simple fact, so either you're wrong or what you're describing is not a >> > program, not an algorithm and not a computation. >> OK, it depends on what you mean by "program". If you presume that a >> program >> can't access its "hardware", > > > I *do not presume it*... it's a *fact*. > > Well, I presented a model of a program that can do that (on some level, not on the level of physical hardware), and is a program in the most fundamental way (doing step-by-step execution of instructions). All you need is a program hierarchy where some programs have access to programs that are below them in the hierarchy (which are the "hardware" though not the *hardware*). So apparently it is not so much a fact about programs in a common sense way, but about a narrow conception of what programs can be. benjayk -- View this message in context: http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34417762.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.
Re: Why the Church-Turing thesis?
2012/9/11 benjayk > > > Quentin Anciaux-2 wrote: > > > > 2012/9/11 benjayk > > > >> > >> > >> Quentin Anciaux-2 wrote: > >> > > >> > 2012/9/10 benjayk > >> > > >> >> > >> >> > >> >> > > No program can determine its hardware. This is a consequence of > >> the > >> >> > > Church > >> >> > > Turing thesis. The particular machine at the lowest level has no > >> >> > bearing > >> >> > > (from the program's perspective). > >> >> > If that is true, we can show that CT must be false, because we > *can* > >> >> > define > >> >> > a "meta-program" that has access to (part of) its own hardware > >> (which > >> >> > still > >> >> > is intuitively computable - we can even implement it on a > computer). > >> >> > > >> >> > >> >> It's false, the program *can't* know that the hardware it has access > >> to > >> >> is > >> >> the *real* hardware and not a simulated hardware. The program has > only > >> >> access to hardware through IO, and it can't tell (as never ever) from > >> >> that > >> >> interface if what's outside is the *real* outside or simulated > >> outside. > >> >> <\quote> > >> >> Yes that is true. If anything it is true because the hardware is not > >> even > >> >> clearly determined at the base level (quantum uncertainty). > >> >> I should have expressed myself more accurately and written " > >> "hardware" > >> " > >> >> or > >> >> "relative 'hardware'". We can define a (meta-)programs that have > >> access > >> >> to > >> >> their "hardware" in the sense of knowing what they are running on > >> >> relative > >> >> to some notion of "hardware". They cannot be emulated using universal > >> >> turing > >> >> machines > >> > > >> > > >> > Then it's not a program if it can't run on a universal turing machine. > >> > > >> The funny thing is, it *can* run on a universal turing machine. Just > that > >> it > >> may lose relative correctness if we do that. > > > > > > Then you must be wrong... I don't understand your point. If it's a > program > > it has access to the "outside" through IO, hence it is impossible for a > > program to differentiate "real" outside from simulated outside... It's a > > simple fact, so either you're wrong or what you're describing is not a > > program, not an algorithm and not a computation. > OK, it depends on what you mean by "program". If you presume that a program > can't access its "hardware", I *do not presume it*... it's a *fact*. Quentin > then what I am describing is indeed not a > program. > > But most definitions don't preclude that. Carrying out instructions > precisely and step-by-step can be done with or without access to your > hardware. > > Anyway, meta-programs can be instantiated using real computer (a program > can, in principle, know and utilize part of a more basic computational > layer > if programmed correctly), so we at least know that real computers are > beyond > turing machines. > > benjayk > > -- > View this message in context: > http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34417676.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. > > -- All those moments will be lost in time, like tears in rain. -- 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.
Re: Why the Church-Turing thesis?
Quentin Anciaux-2 wrote: > > 2012/9/11 benjayk > >> >> >> Quentin Anciaux-2 wrote: >> > >> > 2012/9/10 benjayk >> > >> >> >> >> >> >> > > No program can determine its hardware. This is a consequence of >> the >> >> > > Church >> >> > > Turing thesis. The particular machine at the lowest level has no >> >> > bearing >> >> > > (from the program's perspective). >> >> > If that is true, we can show that CT must be false, because we *can* >> >> > define >> >> > a "meta-program" that has access to (part of) its own hardware >> (which >> >> > still >> >> > is intuitively computable - we can even implement it on a computer). >> >> > >> >> >> >> It's false, the program *can't* know that the hardware it has access >> to >> >> is >> >> the *real* hardware and not a simulated hardware. The program has only >> >> access to hardware through IO, and it can't tell (as never ever) from >> >> that >> >> interface if what's outside is the *real* outside or simulated >> outside. >> >> <\quote> >> >> Yes that is true. If anything it is true because the hardware is not >> even >> >> clearly determined at the base level (quantum uncertainty). >> >> I should have expressed myself more accurately and written " >> "hardware" >> " >> >> or >> >> "relative 'hardware'". We can define a (meta-)programs that have >> access >> >> to >> >> their "hardware" in the sense of knowing what they are running on >> >> relative >> >> to some notion of "hardware". They cannot be emulated using universal >> >> turing >> >> machines >> > >> > >> > Then it's not a program if it can't run on a universal turing machine. >> > >> The funny thing is, it *can* run on a universal turing machine. Just that >> it >> may lose relative correctness if we do that. > > > Then you must be wrong... I don't understand your point. If it's a program > it has access to the "outside" through IO, hence it is impossible for a > program to differentiate "real" outside from simulated outside... It's a > simple fact, so either you're wrong or what you're describing is not a > program, not an algorithm and not a computation. OK, it depends on what you mean by "program". If you presume that a program can't access its "hardware", then what I am describing is indeed not a program. But most definitions don't preclude that. Carrying out instructions precisely and step-by-step can be done with or without access to your hardware. Anyway, meta-programs can be instantiated using real computer (a program can, in principle, know and utilize part of a more basic computational layer if programmed correctly), so we at least know that real computers are beyond turing machines. benjayk -- View this message in context: http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34417676.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.
Re: Why the Church-Turing thesis?
2012/9/11 benjayk > > > Quentin Anciaux-2 wrote: > > > > 2012/9/10 benjayk > > > >> > >> > >> > > No program can determine its hardware. This is a consequence of the > >> > > Church > >> > > Turing thesis. The particular machine at the lowest level has no > >> > bearing > >> > > (from the program's perspective). > >> > If that is true, we can show that CT must be false, because we *can* > >> > define > >> > a "meta-program" that has access to (part of) its own hardware (which > >> > still > >> > is intuitively computable - we can even implement it on a computer). > >> > > >> > >> It's false, the program *can't* know that the hardware it has access to > >> is > >> the *real* hardware and not a simulated hardware. The program has only > >> access to hardware through IO, and it can't tell (as never ever) from > >> that > >> interface if what's outside is the *real* outside or simulated outside. > >> <\quote> > >> Yes that is true. If anything it is true because the hardware is not > even > >> clearly determined at the base level (quantum uncertainty). > >> I should have expressed myself more accurately and written " "hardware" > " > >> or > >> "relative 'hardware'". We can define a (meta-)programs that have access > >> to > >> their "hardware" in the sense of knowing what they are running on > >> relative > >> to some notion of "hardware". They cannot be emulated using universal > >> turing > >> machines > > > > > > Then it's not a program if it can't run on a universal turing machine. > > > The funny thing is, it *can* run on a universal turing machine. Just that > it > may lose relative correctness if we do that. Then you must be wrong... I don't understand your point. If it's a program it has access to the "outside" through IO, hence it is impossible for a program to differentiate "real" outside from simulated outside... It's a simple fact, so either you're wrong or what you're describing is not a program, not an algorithm and not a computation. Quentin > We can still use a turing > machine to "run" it and interpret what the result means. > > So for all intents and purposes it is quite like a program. Maybe not a > program as such, OK, but it certainly can be used precisely in a > step-by-step manner, and I think this is what CT thesis means by > algorithmically computable. > Maybe not, but in this case CT is just a statement about specific forms of > algorithms. > > -- > View this message in context: > http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34417440.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. > > -- All those moments will be lost in time, like tears in rain. -- 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.
Re: Why the Church-Turing thesis?
Quentin Anciaux-2 wrote: > > 2012/9/10 benjayk > >> >> >> > > No program can determine its hardware. This is a consequence of the >> > > Church >> > > Turing thesis. The particular machine at the lowest level has no >> > bearing >> > > (from the program's perspective). >> > If that is true, we can show that CT must be false, because we *can* >> > define >> > a "meta-program" that has access to (part of) its own hardware (which >> > still >> > is intuitively computable - we can even implement it on a computer). >> > >> >> It's false, the program *can't* know that the hardware it has access to >> is >> the *real* hardware and not a simulated hardware. The program has only >> access to hardware through IO, and it can't tell (as never ever) from >> that >> interface if what's outside is the *real* outside or simulated outside. >> <\quote> >> Yes that is true. If anything it is true because the hardware is not even >> clearly determined at the base level (quantum uncertainty). >> I should have expressed myself more accurately and written " "hardware" " >> or >> "relative 'hardware'". We can define a (meta-)programs that have access >> to >> their "hardware" in the sense of knowing what they are running on >> relative >> to some notion of "hardware". They cannot be emulated using universal >> turing >> machines > > > Then it's not a program if it can't run on a universal turing machine. > The funny thing is, it *can* run on a universal turing machine. Just that it may lose relative correctness if we do that. We can still use a turing machine to "run" it and interpret what the result means. So for all intents and purposes it is quite like a program. Maybe not a program as such, OK, but it certainly can be used precisely in a step-by-step manner, and I think this is what CT thesis means by algorithmically computable. Maybe not, but in this case CT is just a statement about specific forms of algorithms. -- View this message in context: http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34417440.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.
Re: Why the Church-Turing thesis?
On 9/10/2012 11:40 AM, benjayk wrote: No program can determine its hardware. This is a consequence of the Church Turing thesis. The particular machine at the lowest level has no bearing (from the program's perspective). If that is true, we can show that CT must be false, because we *can* define a "meta-program" that has access to (part of) its own hardware (which still is intuitively computable - we can even implement it on a computer). It's false, the program *can't* know that the hardware it has access to is the *real* hardware and not a simulated hardware. The program has only access to hardware through IO, and it can't tell (as never ever) from that interface if what's outside is the *real* outside or simulated outside. <\quote> Yes that is true. If anything it is true because the hardware is not even clearly determined at the base level (quantum uncertainty). I should have expressed myself more accurately and written " "hardware" " or "relative 'hardware'". We can define a (meta-)programs that have access to their "hardware" in the sense of knowing what they are running on relative to some notion of "hardware". They cannot be emulated using universal turing machines (in general - in specific instances, where the hardware is fixed on the right level, they might be). They can be simulated, though, but in this case the simulation may be incorrect in the given context and we have to put it into the right context to see what it is actually emulating (not the meta-program itself, just its behaviour relative to some other context). We can also define an infinite hierarchy of meta-meta--programs (n metas) to show that there is no universal notion of computation at all. There is always a notion of computation that is more powerful than the current one, because it can reflect more deeply upon its own "hardware". See my post concerning meta-programs for further details. Dear benjayk, Is there any means by which the resource requirements paly a role for a single program? No, because of this indeterminacy (the 1p indeterminacy) as Bruno has explained well. But while this is true, if you consider multiple computations that are accessing shared resources things are not so clear. I wish that some thought might be given to the problem of concurrency. -- Onward! Stephen http://webpages.charter.net/stephenk1/Outlaw/Outlaw.html -- 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.
Re: Why the Church-Turing thesis?
2012/9/10 benjayk > > > > > No program can determine its hardware. This is a consequence of the > > > Church > > > Turing thesis. The particular machine at the lowest level has no > > bearing > > > (from the program's perspective). > > If that is true, we can show that CT must be false, because we *can* > > define > > a "meta-program" that has access to (part of) its own hardware (which > > still > > is intuitively computable - we can even implement it on a computer). > > > > It's false, the program *can't* know that the hardware it has access to is > the *real* hardware and not a simulated hardware. The program has only > access to hardware through IO, and it can't tell (as never ever) from that > interface if what's outside is the *real* outside or simulated outside. > <\quote> > Yes that is true. If anything it is true because the hardware is not even > clearly determined at the base level (quantum uncertainty). > I should have expressed myself more accurately and written " "hardware" " > or > "relative 'hardware'". We can define a (meta-)programs that have access to > their "hardware" in the sense of knowing what they are running on relative > to some notion of "hardware". They cannot be emulated using universal > turing > machines Then it's not a program if it can't run on a universal turing machine. > (in general - in specific instances, where the hardware is fixed on > the right level, they might be). They can be simulated, though, but in this > case the simulation may be incorrect in the given context and we have to > put > it into the right context to see what it is actually emulating (not the > meta-program itself, just its behaviour relative to some other context). > > We can also define an infinite hierarchy of meta-meta--programs (n > metas) to show that there is no universal notion of computation at all. > There is always a notion of computation that is more powerful than the > current one, because it can reflect more deeply upon its own "hardware". > > See my post concerning meta-programs for further details. > -- > View this message in context: > http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34413719.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. > > -- All those moments will be lost in time, like tears in rain. -- 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.
Re: Why the Church-Turing thesis?
> > No program can determine its hardware. This is a consequence of the > > Church > > Turing thesis. The particular machine at the lowest level has no > bearing > > (from the program's perspective). > If that is true, we can show that CT must be false, because we *can* > define > a "meta-program" that has access to (part of) its own hardware (which > still > is intuitively computable - we can even implement it on a computer). > It's false, the program *can't* know that the hardware it has access to is the *real* hardware and not a simulated hardware. The program has only access to hardware through IO, and it can't tell (as never ever) from that interface if what's outside is the *real* outside or simulated outside. <\quote> Yes that is true. If anything it is true because the hardware is not even clearly determined at the base level (quantum uncertainty). I should have expressed myself more accurately and written " "hardware" " or "relative 'hardware'". We can define a (meta-)programs that have access to their "hardware" in the sense of knowing what they are running on relative to some notion of "hardware". They cannot be emulated using universal turing machines (in general - in specific instances, where the hardware is fixed on the right level, they might be). They can be simulated, though, but in this case the simulation may be incorrect in the given context and we have to put it into the right context to see what it is actually emulating (not the meta-program itself, just its behaviour relative to some other context). We can also define an infinite hierarchy of meta-meta--programs (n metas) to show that there is no universal notion of computation at all. There is always a notion of computation that is more powerful than the current one, because it can reflect more deeply upon its own "hardware". See my post concerning meta-programs for further details. -- View this message in context: http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34413719.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.
Re: Why the Church-Turing thesis?
running > > our universe. > Do you realize that what you said is just a restatement of the belief in > "only low level computation matters"? I think if the universe were an > emulation we could indeed see no difference, because we wouldn't be in the > emulation at all (though our behaviour may be mirrored in some way there). > > > Jason Resch-2 wrote: > > > > > >> Jason Resch-2 wrote: > >> > > >> >> > >> >> Even if we grant that what you say is true, why would we define > >> >> computation > >> >> as being completely abstracted from the way something is expressed? > >> >> Especially if languages are very different (and programming languages > >> can > >> >> be > >> >> *very* different) the way we express actually does matter so much > that > >> it > >> >> is > >> >> quite meaningless to even say the express the same thing. > >> >> > >> >> Tell me, does "" really > >> >> practically express the same thing as "44"? > >> > > >> > > >> > It depends on the interpreter. > >> Right. And this means that the strings practically will express > different > >> things and are thus not equivalent in general. The same is true for > >> computations. > >> > > > > A Turing machine along with its tape has a unique definition and future > > evolution. All the meaning it has is also uniquely defined (though > > perhaps > > implicitly), anyone can follow it and see what it does. > That's not true. The low-level action of a turing machine may have many > high-level meanings, which can't be derived from the lower levels. For > example, it is possible that some operation on data may represent graphical > transformation, or change to a source code of a program, or change of an > audio file, etc... > > It only practically mostly isn't the case because we encode and store and > manipulate and decode the data in a way that is mostly not very ambigous > (to > us!). But that is a function of a higher-level. The computer itself doesn't > know what data represents. We can use computers do display images as texts > for example, and if we lack the right interpretational layer, then a given > piece of data, or a given computatation is just meaingless rubbish. > > > Jason Resch-2 wrote: > > > > Whereas with a lone bit string (with no definition of its interpreter), > > there is no > > inherent or definite meaning. > Yes, just as with turing machines. > The only inherent meaning of a bit string like 01 is first bit is zero, > second bit is 1. > > Very long bit strings can have quite unique high-level meaning for us, just > like long computations. > > > Jason Resch-2 wrote: > > > >> > >> > >> Jason Resch-2 wrote: > >> > > >> >> will be easy to read, will be easily interpreted without error, > >> >> will be easier to correctly use, etc... > >> >> So using different symbols will expand what the system can express on > >> a > >> >> very > >> >> relevant level. > >> >> > >> > > >> > At the lowest level but not at higher levels. You are using a > computer > >> to > >> > type an email which uses a "tape" that has only 2 states. Yet you are > >> > still able to type "44". > >> ??? > >> Did you mean at the higher level, but not at the lowest level? > >> > > > > By lowest level I mean the raw hardware. At the lowest level your > > computer's memory can only represent 2 states, often labeled '1' and '0'. > > But at the higher levels built upon this, you can have programs with much > > larger symbol sets. > > > > Maybe this is the source of our confusion and disagreement? > Yes, it seems like it. You say that the higher levels are contained in the > lower level, while I argue that they are clearly not, though they may be > relatively to a representational meta-level (but only because we use the > low > levels in the right way - which is big feat in itself). > > > Jason Resch-2 wrote: > > > >> > The computer (any computer) can do the interpretation for us. You can > >> > enter a description of the machine at one point in time, and the state > >> of > >> > the machine at another time, and ask the computer is this th
Re: Why the Church-Turing thesis?
As far as I see, we mostly agree on content. I just can't make sense of reducing computation to emulability. For me the intuitive sene of computation is much more rich than this. But still, as I think about it, we can also create a model of computation (in the sense of being intuitively computational and being implementable on a computer) where there are computations that can't be emulated by universal turing machine, using "level breaking" languages (which explicitly refer to what is being computed on the base level). I'll write another post on this. benjayk -- View this message in context: http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34406986.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.
Re: Why the Church-Turing thesis?
eneral. The same is true for >> computations. >> > > A Turing machine along with its tape has a unique definition and future > evolution. All the meaning it has is also uniquely defined (though > perhaps > implicitly), anyone can follow it and see what it does. That's not true. The low-level action of a turing machine may have many high-level meanings, which can't be derived from the lower levels. For example, it is possible that some operation on data may represent graphical transformation, or change to a source code of a program, or change of an audio file, etc... It only practically mostly isn't the case because we encode and store and manipulate and decode the data in a way that is mostly not very ambigous (to us!). But that is a function of a higher-level. The computer itself doesn't know what data represents. We can use computers do display images as texts for example, and if we lack the right interpretational layer, then a given piece of data, or a given computatation is just meaingless rubbish. Jason Resch-2 wrote: > > Whereas with a lone bit string (with no definition of its interpreter), > there is no > inherent or definite meaning. Yes, just as with turing machines. The only inherent meaning of a bit string like 01 is first bit is zero, second bit is 1. Very long bit strings can have quite unique high-level meaning for us, just like long computations. Jason Resch-2 wrote: > >> >> >> Jason Resch-2 wrote: >> > >> >> will be easy to read, will be easily interpreted without error, >> >> will be easier to correctly use, etc... >> >> So using different symbols will expand what the system can express on >> a >> >> very >> >> relevant level. >> >> >> > >> > At the lowest level but not at higher levels. You are using a computer >> to >> > type an email which uses a "tape" that has only 2 states. Yet you are >> > still able to type "44". >> ??? >> Did you mean at the higher level, but not at the lowest level? >> > > By lowest level I mean the raw hardware. At the lowest level your > computer's memory can only represent 2 states, often labeled '1' and '0'. > But at the higher levels built upon this, you can have programs with much > larger symbol sets. > > Maybe this is the source of our confusion and disagreement? Yes, it seems like it. You say that the higher levels are contained in the lower level, while I argue that they are clearly not, though they may be relatively to a representational meta-level (but only because we use the low levels in the right way - which is big feat in itself). Jason Resch-2 wrote: > >> > The computer (any computer) can do the interpretation for us. You can >> > enter a description of the machine at one point in time, and the state >> of >> > the machine at another time, and ask the computer is this the state the >> > machine will be in N steps from now. Where 0 is no and 1 is yes, or A >> is >> > no and B is yes, or X is no and Y is yes. Whatever symbols it might >> use, >> > any computer can be setup to answer questions about any other machine >> in >> > this way. >> The computer will just output zeroes and ones, and the screen will >> convert >> this into pixels. Without your interpretation the pixels (and thus the >> answers) are meaningless. >> > > When things make a difference, they aren't meaningless. The register > containing a value representing a plane's altitude isn't meaningless to > the > autopilot program, nor to those on board. Right, but it is meaningless on the level we are speaking about. If you use a turing machine to emulate another, more complex one, than its output is meaningless until you interpret it the right way. Jason Resch-2 wrote: > >> If you don't know how to encode and decode the symbols (ie interpret them >> on >> a higher level than the level of the interpretation the machine is doing) >> the "interpretation" is useless. >> > > Useless to the one who failed to interpret them, but perhaps not > generally. If you were dropped off in a foreign land, your speech would > be > meaningless to others who heard you, but not to you, or others who know > how to interpret it. Right. I am not objecting to this. But this is precisely why we can't ignore the higher levels as being less important (or even irrelevant) than the low level language / computation. Unless we postulate some independent higher level, the lower levels don't make sense in a high level context (like emulation only makes sense to some observer that knows of the existence of different machines). Jason Resch-2 wrote: > > >> We always have to have some information beforehand (though it may be >> implicit, without being communicated first). Otherwise every signal is >> useless because it could mean everything and nothing. >> >> > How do infants learn language if they start with none? Because they still have something, even though it is not a language in our sense. Of course we can get from no information to some information in some relative realm. benjayk -- View this message in context: http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34406957.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.
Re: Why the Church-Turing thesis?
nsional CT, which follows easily by the "enumeration theorem", which is the standard name asserting the existence of universal machine in each such universal class of computable functions. Why are two machines that can be used to emlate each other regarded to be equivalent? They are equivalment with respect of the computability/emulability issue, but not on provability, knowability, sensibility, etc. Thay might still argue about which movie to look on TV! In my view, there is a big difference between computing the same and being able to emulate each other. Most importantly, emulation only makes sense relative to another machine that is being emulated, and a correct interpretation. By the intensional CT, emulation is like computation. Bruno benjayk -- View this message in context: http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34401986.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 . http://iridia.ulb.ac.be/~marchal/ -- 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.
Re: Why the Church-Turing thesis?
On 9/7/2012 6:24 AM, benjayk wrote: Why are two machines that can be used to emlate each other regarded to be equivalent? In my view, there is a big difference between computing the same and being able to emulate each other. Most importantly, emulation only makes sense relative to another machine that is being emulated, and a correct interpretation. Dear benjayk, This is what is discussed under the header of "Bisimilarity" and bisimulation equivalence iff simulation = emulation. http://en.wikipedia.org/wiki/Bisimulation "a bisimulation is a binary relation between state transition systems, associating systems which behave in the same way in the sense that one system simulates the other and vice-versa." My own use of the term seeks a more generalized version that does not assume that the relation is necessarily binary nor strictly monotonic. The key is that a pair of machines can have an "image" of each other and that they are capable of acting on that image. -- Onward! Stephen http://webpages.charter.net/stephenk1/Outlaw/Outlaw.html -- 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.
Re: Why the Church-Turing thesis?
gt; >> It is true in a very limited sense, but it seems mad to treat >> >> it as the foundation of what it means for words to express something >> (and >> >> the same goes for computation). >> >> If we use such trivial notions of computation, why not say that the >> >> program >> >> "return input" emulates all turing-machines because given the right >> input >> >> it >> >> gives the right output (we just give it the solution as input). >> >> >> > >> > Many programs have no input and/or no output, but they still can be >> > rightfully said to perform different computations. >> OK. Then we use the same program but demand as input the correct >> development >> of the execution of the program (use it multiple times if you haven't >> emulated enough steps). >> You see? We can trivialize the notion of computation as much as we like, >> by >> adding more and more layers of interpretation, or more demands on the >> right >> usage of the program. It just doesn't make sense to pretend that this >> trivalization actually is what computation is. >> Sure, my example is a lot more useless than the CT notion of computation, >> but it is the same principle. Abstracting and interpreting until we >> arrive >> at a trivialization of the actual phenomenon. >> > > The computer (any computer) can do the interpretation for us. You can > enter a description of the machine at one point in time, and the state of > the machine at another time, and ask the computer is this the state the > machine will be in N steps from now. Where 0 is no and 1 is yes, or A is > no and B is yes, or X is no and Y is yes. Whatever symbols it might use, > any computer can be setup to answer questions about any other machine in > this way. The computer will just output zeroes and ones, and the screen will convert this into pixels. Without your interpretation the pixels (and thus the answers) are meaningless. If you don't know how to encode and decode the symbols (ie interpret them on a higher level than the level of the interpretation the machine is doing) the "interpretation" is useless. The computer always only does low level interpretations. Jason Resch-2 wrote: > >> >> A turing machine by itself simply doesn't emulate anything. We just >> provide >> it input and interpret its output to emulate something *using* a turing >> machine. >> > > So computers don't add, don't compare, don't increment numbers unless a > particular person looks at it and gives a notarized stamp attesting to the > action being performed? I talked about emulating, not computing in general. Jason Resch-2 wrote: > >> By correctly interpreting, we can use any symbols for anything. We "just" >> have to interpret them correctly. So this symbol tells you how to build >> an >> very advanced AI: "°". Of course you still have to interpret what it >> means. >> ;) >> > > There are limits though. You can't communicate a message that contains > more than a amount of informational of entropy without sending a certain > number of symbols. Nope. If I have the right information beforehand, I can send an unlimited amount of information using only one bit (using an agreement like "if we you send me one bit in the next hour, then this means XYZ..."). We always have to have some information beforehand (though it may be implicit, without being communicated first). Otherwise every signal is useless because it could mean everything and nothing. Jason Resch-2 wrote: > >> The same really applies to turing machines on a different level. A turing >> machine is indeed utterly useless to perform actual, complex, real life >> computation. >> > > Can you provide an example of such an actual, complex, real life > computation? Playing a modern computer game. You won't find a turing machine that you can play a game on. benjayk -- View this message in context: http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34402167.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.
Re: Why the Church-Turing thesis?
Bruno Marchal wrote:
>
>
> On 28 Aug 2012, at 21:57, benjayk wrote:
>
>>
>> It seems that the Church-Turing thesis, that states that an
>> universal turing
>> machine can compute everything that is intuitively computable, has
>> near
>> universal acceptance among computer scientists.
>
> Yes indeed. I think there are two strong arguments for this.
>
> The empirical one: all attempts to define the set of computable
> functions have led to the same class of functions, and this despite
> the quite independent path leading to the definitions (from Church
> lambda terms, Post production systems, von Neumann machine, billiard
> ball, combinators, cellular automata ... up to modular functor,
> quantum topologies, quantum computers, etc.).
>
OK, now I understand it better. Apparently if we express a computation in
terms of a computable function we can always arrive at the same computable
function using a different computation of an abitrary turing universal
machine. That seems right to me.
But in this case I don't get why it is often claimed that CT thesis claims
that all computations can be done by a universal turing machine, not merely
that they lead to the same class of computable functions (if "converted"
appriopiately).
The latter is a far weaker statement, since computable functions abstract
from many relevant things about the machine.
And even this weaker statement doesn't seem true with regards to more
powerful models like super-recursive functions, as computable functions just
give finite results, while super-recursive machine can give
infinite/unlimited results.
Bruno Marchal wrote:
>
> The conceptual one: the class of computable functions is closed for
> the most transcendental operation in math: diagonalization. This is
> not the case for the notions of definability, provability,
> cardinality, etc.
I don't really know what this means. Do you mean that there are just
countable many computations? If yes, what has this do with whether all
universal turing machines are equivalent?
Bruno Marchal wrote:
>
>>
>> I really wonder why this is so, given that there are simple cases
>> where we
>> can compute something that an abitrary turing machine can not
>> compute using
>> a notion of computation that is not extraordinary at all (and quite
>> relevant
>> in reality).
>> For example, given you have a universal turing machine A that uses the
>> alphabet {1,0} and a universal turing machine B that uses the alphabet
>> {-1,0,1}.
>> Now it is quite clear that the machine A cannot directly answer any
>> questions that relates to -1. For example it cannot directly compute
>> -1*-1=1. Machine A can only be used to use an encoded input value and
>> encoded description of machine B, and give an output that is correct
>> given
>> the right decoding scheme.
>> But for me this already makes clear that machine A is less
>> computationally
>> powerful than machine B.
>
> Church thesis concerns only the class of computable functions.
Hm, maybe the wikipedia article is a bad one, since it mentioned computable
functions just as means of explaining it, not as part of its definition.
Bruno Marchal wrote:
>
> The alphabet used by the Turing machine, having 1, 2, or enumerable
> alphabet does not change the class. If you dovetail on the works of 1
> letter Turing machine, you will unavoidably emulate all Turing
> machines on all finite and enumerable letters alphabets. This can be
> proved. Nor does the number of tapes, and/or parallelism change that
> class.
> Of course, some machine can be very inefficient, but this, by
> definition, does not concern Church thesis.
Even so, CT thesis makes a claim about the equivalence of machines, not of
emulability.
Why are two machines that can be used to emlate each other regarded to be
equivalent?
In my view, there is a big difference between computing the same and being
able to emulate each other. Most importantly, emulation only makes sense
relative to another machine that is being emulated, and a correct
interpretation.
benjayk
--
View this message in context:
http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34401986.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.
Re: Why the Church-Turing thesis?
On 28 Aug 2012, at 21:57, benjayk wrote:
It seems that the Church-Turing thesis, that states that an
universal turing
machine can compute everything that is intuitively computable, has
near
universal acceptance among computer scientists.
Yes indeed. I think there are two strong arguments for this.
The empirical one: all attempts to define the set of computable
functions have led to the same class of functions, and this despite
the quite independent path leading to the definitions (from Church
lambda terms, Post production systems, von Neumann machine, billiard
ball, combinators, cellular automata ... up to modular functor,
quantum topologies, quantum computers, etc.).
The conceptual one: the class of computable functions is closed for
the most transcendental operation in math: diagonalization. This is
not the case for the notions of definability, provability,
cardinality, etc.
I really wonder why this is so, given that there are simple cases
where we
can compute something that an abitrary turing machine can not
compute using
a notion of computation that is not extraordinary at all (and quite
relevant
in reality).
For example, given you have a universal turing machine A that uses the
alphabet {1,0} and a universal turing machine B that uses the alphabet
{-1,0,1}.
Now it is quite clear that the machine A cannot directly answer any
questions that relates to -1. For example it cannot directly compute
-1*-1=1. Machine A can only be used to use an encoded input value and
encoded description of machine B, and give an output that is correct
given
the right decoding scheme.
But for me this already makes clear that machine A is less
computationally
powerful than machine B.
Church thesis concerns only the class of computable functions. The
alphabet used by the Turing machine, having 1, 2, or enumerable
alphabet does not change the class. If you dovetail on the works of 1
letter Turing machine, you will unavoidably emulate all Turing
machines on all finite and enumerable letters alphabets. This can be
proved. Nor does the number of tapes, and/or parallelism change that
class.
Of course, some machine can be very inefficient, but this, by
definition, does not concern Church thesis.
There was a thesis, often attributed to Cook (but I met him and he
claims it is not his thesis), that all Turing machine can emulate
themselves in polynomial time. This will plausibly be refuted by the
existence of quantum computers (unless P = NP, or things like that).
It is an open problem, but most scientists believe that in general a
classical computer cannot emulate an arbitrary quantum computer in
polynomial time. But I insist, quantum computer have not violated the
Church Turing Post Markov thesis.
Its input and output when emulating B do only make
sense with respect to what the machine B does if we already know what
machine B does, and if it is known how we chose to reflect this in
the input
of machine A (and the interpretation of its output). Otherwise we
have no
way of even saying whether it emulates something, or whether it is
just
doing a particular computation on the alphabet {1,0}.
I realize that it all comes down to the notion of computation. But
why do
most choose to use such a weak notion of computation? How does
machine B not
compute something that A doesn't by any reasonable standard?
Saying that A can compute what B computes is like saying that
"orange" can
express the same as the word "apple", because we can encode the word
"apple"
as "orange". It is true in a very limited sense, but it seems mad to
treat
it as the foundation of what it means for words to express something
(and
the same goes for computation).
If we use such trivial notions of computation, why not say that the
program
"return input" emulates all turing-machines because given the right
input it
gives the right output (we just give it the solution as input).
I get that we can simply use the Church-turing as the definition of
computation means. But why is it (mostly) treated as being the one
and only
correct notion of computation (especially in a computer science
context)?
The only explanation I have is that it is dogma. To question it
would change
to much and would be too "complicated" and uncomfortable. It would
make
computation an irreducibly complex and relative notion or - heaven
forbid -
even an inherently subjective notion (computation from which
perspective?).
That was what everybody believed before the rise of the universal
machine and lambda calculus. Gödel called the closure of the
computable functions for diagonalization a "miracle", and he took time
before assessing it. See:
DAVIS M., 1982, Why Gödel Didn't Have Church's Thesis, Information and
Control
54,.pp. 3-24.
http://iridia.ulb.ac.be/~marchal/
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To
Re: Why the Church-Turing thesis?
y. So this symbol tells you how to build an > very advanced AI: "°". Of course you still have to interpret what it means. > ;) > There are limits though. You can't communicate a message that contains more than a amount of informational of entropy without sending a certain number of symbols. > > > Jason Resch-2 wrote: > > > >> I get that we can simply use the Church-turing as the definition of > >> computation means. But why is it (mostly) treated as being the one and > >> only > >> correct notion of computation (especially in a computer science > context)? > > > > > > I think it more comes into play in the a definition of a universal > > machine, > > than in the definition of computation. > > > > It is useful because it makes it easy to prove. All you need to do is > > show > > how some machine can be used to emulate any other known turning universal > > machine. > Well, every machine that can output its input can emulate any turing > machine, only in a utterly trivial and useless way (just give it the > correct > emulation as input). > Emulations aren't static bit strings, they involve changes in state and counterfactuals. > The same really applies to turing machines on a different level. A turing > machine is indeed utterly useless to perform actual, complex, real life > computation. > Can you provide an example of such an actual, complex, real life computation? Jason > > > Jason Resch-2 wrote: > > > >> > > > > The only explanation I have is that it is dogma. To question it would > > change > >> to much and would be too "complicated" and uncomfortable. It would make > >> computation an irreducibly complex and relative notion or - heaven > forbid > >> - > >> even an inherently subjective notion (computation from which > >> perspective?). > > > > > > Reverse engineering machine language code is very difficult, but there > are > > automated programs for doing this that can provide much more readable > > program code. Code too, can be difficult to grasp, (see > > http://www.ioccc.org/ for example), but in other cases, code is easy to > > understand. I often prefer a snippet of example code to a notation-heavy > > mathematical formula. > > > OK, but I don't get the relation to what I wrote. > > benjayk > > -- > View this message in context: > http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34398854.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. > > -- 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.
Re: Why the Church-Turing thesis?
achine by itself simply doesn't emulate anything. We just provide it input and interpret its output to emulate something *using* a turing machine. Only by senselessly abstracting away the crucial steps of encoding, decoding and interpreting we arrive at the CT thesis. By correctly interpreting, we can use any symbols for anything. We "just" have to interpret them correctly. So this symbol tells you how to build an very advanced AI: "°". Of course you still have to interpret what it means. ;) Jason Resch-2 wrote: > >> I get that we can simply use the Church-turing as the definition of >> computation means. But why is it (mostly) treated as being the one and >> only >> correct notion of computation (especially in a computer science context)? > > > I think it more comes into play in the a definition of a universal > machine, > than in the definition of computation. > > It is useful because it makes it easy to prove. All you need to do is > show > how some machine can be used to emulate any other known turning universal > machine. Well, every machine that can output its input can emulate any turing machine, only in a utterly trivial and useless way (just give it the correct emulation as input). The same really applies to turing machines on a different level. A turing machine is indeed utterly useless to perform actual, complex, real life computation. Jason Resch-2 wrote: > >> > > The only explanation I have is that it is dogma. To question it would > change >> to much and would be too "complicated" and uncomfortable. It would make >> computation an irreducibly complex and relative notion or - heaven forbid >> - >> even an inherently subjective notion (computation from which >> perspective?). > > > Reverse engineering machine language code is very difficult, but there are > automated programs for doing this that can provide much more readable > program code. Code too, can be difficult to grasp, (see > http://www.ioccc.org/ for example), but in other cases, code is easy to > understand. I often prefer a snippet of example code to a notation-heavy > mathematical formula. > OK, but I don't get the relation to what I wrote. benjayk -- View this message in context: http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34398854.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.
Re: Why the Church-Turing thesis?
On Tue, Aug 28, 2012 at 2:57 PM, benjayk wrote:
>
> It seems that the Church-Turing thesis, that states that an universal
> turing
> machine can compute everything that is intuitively computable, has near
> universal acceptance among computer scientists.
>
> I really wonder why this is so, given that there are simple cases where we
> can compute something that an abitrary turing machine can not compute using
> a notion of computation that is not extraordinary at all (and quite
> relevant
> in reality).
> For example, given you have a universal turing machine A that uses the
> alphabet {1,0} and a universal turing machine B that uses the alphabet
> {-1,0,1}.
> Now it is quite clear that the machine A cannot directly answer any
> questions that relates to -1. For example it cannot directly compute
> -1*-1=1. Machine A can only be used to use an encoded input value and
> encoded description of machine B, and give an output that is correct given
> the right decoding scheme.
>
1's or 0's, X's or O's, what the symbols are don't have any bearing on what
they can compute.
Consider: No physical computer today uses 1's or 0's, they use voltages,
collections of more or fewer electrons.
This doesn't mean that our computers can only directly compute what
electrons do.
But for me this already makes clear that machine A is less computationally
> powerful than machine B. Its input and output when emulating B do only make
> sense with respect to what the machine B does if we already know what
> machine B does, and if it is known how we chose to reflect this in the
> input
> of machine A (and the interpretation of its output). Otherwise we have no
> way of even saying whether it emulates something, or whether it is just
> doing a particular computation on the alphabet {1,0}.
>
These are rather convincing:
http://en.wikipedia.org/wiki/Video_game_console_emulator
There is software that emulates the unique architectures of an Atari,
Nintendo, Supernintendo, PlayStation, etc. systems. These emulators can
also run on any computer, whether its Intel X86, x86_64, PowerPC, etc. You
will have a convincing experience of playing an old Atari game like space
invaders, even though the original creators of that program never intended
it to run on a computer architecture that wouldn't be invented for another
30 years, and the original programmers didn't have to be called in to
re-write their program to do so.
> I realize that it all comes down to the notion of computation. But why do
> most choose to use such a weak notion of computation? How does machine B
> not
> compute something that A doesn't by any reasonable standard?
> Saying that A can compute what B computes is like saying that "orange" can
> express the same as the word "apple", because we can encode the word
> "apple"
> as "orange".
System A (using its own language of representation for system A), can
predict exactly all future states of another system B (and vice versa). A
and B have different symbols, states, instructions, etc., so perhaps this
is why you think system A can't perfectly emulate system B, but this is a
little like saying there are things that can only be described by Spanish
speakers that no other language (French, English, etc.) could describe.
Sure, a translation needs to occur to communicate a Spanish idea into an
English one, but just because spanish and english speakers use a different
language doesn't mean there are problems only speakers of one language can
solve.
> It is true in a very limited sense, but it seems mad to treat
> it as the foundation of what it means for words to express something (and
> the same goes for computation).
> If we use such trivial notions of computation, why not say that the program
> "return input" emulates all turing-machines because given the right input
> it
> gives the right output (we just give it the solution as input).
>
Many programs have no input and/or no output, but they still can be
rightfully said to perform different computations.
> I get that we can simply use the Church-turing as the definition of
> computation means. But why is it (mostly) treated as being the one and only
> correct notion of computation (especially in a computer science context)?
I think it more comes into play in the a definition of a universal machine,
than in the definition of computation.
It is useful because it makes it easy to prove. All you need to do is show
how some machine can be used to emulate any other known turning universal
machine.
>
The only explanation I have is that it is dogma. To question it would change
> to much and would be too "complicated" and uncomfortable. It would make
> computation an irreducibly complex and relative notion or - heaven forbid -
> even an inherently subjective notion (computation from which perspective?).
Reverse engineering machine language code is very difficult, but there are
automated programs for doing this that can provide much more readable
program code. Cod
Why the Church-Turing thesis?
It seems that the Church-Turing thesis, that states that an universal turing
machine can compute everything that is intuitively computable, has near
universal acceptance among computer scientists.
I really wonder why this is so, given that there are simple cases where we
can compute something that an abitrary turing machine can not compute using
a notion of computation that is not extraordinary at all (and quite relevant
in reality).
For example, given you have a universal turing machine A that uses the
alphabet {1,0} and a universal turing machine B that uses the alphabet
{-1,0,1}.
Now it is quite clear that the machine A cannot directly answer any
questions that relates to -1. For example it cannot directly compute
-1*-1=1. Machine A can only be used to use an encoded input value and
encoded description of machine B, and give an output that is correct given
the right decoding scheme.
But for me this already makes clear that machine A is less computationally
powerful than machine B. Its input and output when emulating B do only make
sense with respect to what the machine B does if we already know what
machine B does, and if it is known how we chose to reflect this in the input
of machine A (and the interpretation of its output). Otherwise we have no
way of even saying whether it emulates something, or whether it is just
doing a particular computation on the alphabet {1,0}.
I realize that it all comes down to the notion of computation. But why do
most choose to use such a weak notion of computation? How does machine B not
compute something that A doesn't by any reasonable standard?
Saying that A can compute what B computes is like saying that "orange" can
express the same as the word "apple", because we can encode the word "apple"
as "orange". It is true in a very limited sense, but it seems mad to treat
it as the foundation of what it means for words to express something (and
the same goes for computation).
If we use such trivial notions of computation, why not say that the program
"return input" emulates all turing-machines because given the right input it
gives the right output (we just give it the solution as input).
I get that we can simply use the Church-turing as the definition of
computation means. But why is it (mostly) treated as being the one and only
correct notion of computation (especially in a computer science context)?
The only explanation I have is that it is dogma. To question it would change
to much and would be too "complicated" and uncomfortable. It would make
computation an irreducibly complex and relative notion or - heaven forbid -
even an inherently subjective notion (computation from which perspective?).
--
View this message in context:
http://old.nabble.com/Why-the-Church-Turing-thesis--tp34348236p34348236.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.
