On Thursday, August 23, 2018 at 2:01:24 AM UTC, Jason wrote: > > > > On Wed, Aug 22, 2018 at 4:43 PM <[email protected] <javascript:>> wrote: > >> >> >> On Tuesday, August 21, 2018 at 3:22:04 PM UTC, Jason wrote: >>> >>> >>> >>> On Tue, Aug 21, 2018 at 1:16 AM <[email protected]> wrote: >>> >>>> I've been looking at the Wiki article on this topic. I find that I >>>> really don't understand what it is, or why it's important. Maybe a few >>>> succinct words from the usual suspects can be of help. TIA. >>>> >>>> >>>> >>> >>> Bruno provided a great definition and background of the Church-Turing >>> Thesis. I will try to answer why it is important and comes up often in our >>> discussion. >>> >>> >>> The Church-Turing thesis says that anything that is computable is >>> computable by any computer. In other words, there is nothing that the >>> computer in your cell phone can't compute, that your laptop or that a super >>> computer (or even a quantum computer) can. It just comes down to having >>> enough time and memory. >>> >>> This is why you don't need to buy a new phone with new hardware every >>> time you want to install a new app. Regardless of the type of CPU in your >>> phone, it can be extended in its power of what it might compute only given >>> some new software. It is in this sense that computers are "Universal", >>> they are universal in the same sense that of a universal remote, or in the >>> sense that a record player is a universal sound imitating device. A record >>> player might emulate the sounds of an orchestra, Britney Spears, whale >>> songs, etc., all it needs is the appropriate record and it can produce the >>> sound. >>> >>> In the same sense, all a Turing Machine (computer) needs to imitate (or >>> emulate) the right program or function is the right software. Because of >>> this, anything that can be described in software, be it a brain emulation, >>> an AI, a virtual environment, a virtual machine or operating system, can >>> never know what hardware is running it, because the Church-Turing thesis >>> says that any computer is capable of running it. >>> >>> This is why if consciousness is computable (the computational theory of >>> mind) we cannot know what is computing us (e.g. we could be in a matrix >>> type simulation for all we know). The other implication is that if >>> computations exist in mathematics (and they do), then we exist within >>> mathematics. Mathematics (or at least the part necessary to describe >>> computations) becomes the fundamental science of what we experience and >>> what is possible to experience or what we may predict about our future >>> experiences (physics). >>> >>> >>> Jason >>> >> >> If someone digitizes (emulates) the Mona Lisa, is this equivalent to the >> Mona Lisa? >> > > If you digitize a person and put the digitized Mona Lisa before them, it > is equivalent to the real Mona Lisa to that person, at least as far as they > can tell. > > > >> Can you write a function which is not computable? AG >> >> >> > If by not computable you mean it never returns, then this is easy: > > function foo(): > while (true) > { > // loop forever > } > > There are also programs for which no one knows if they are computable or > not. If you can prove whether or not this function ever completes, you > will be world famous, and may even earn a million dollars (though I think > the prize has been retracted, it might be oferred again): > > Step 1: Set X = 4 > Step 2: Set R = 0 > Step 3: For each Y from 1 to X, if both Y and (X – Y) are prime, set R = 1 > Step 4: If R = 1, Set X = X + 2 and go to Step 2 > Step 5: If R = 0, print X and halt > > All you have to prove is the computer either never gets to step 5 or that > it does get to step 5. Mathematicians have been working on a related > problem for 300 years, no one has solved it yet. > > > Jason >
*I was asking about a well-defined mathematical function that can be written in closed form, or possibly as an infinite series. I believe that all such functions are computable. I was not discussing subroutines that might never terminate. If all well defined mathematical functions are computable, why did computability become a big deal? AG * -- You received this message because you are subscribed to the Google Groups "Everything List" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. Visit this group at https://groups.google.com/group/everything-list. For more options, visit https://groups.google.com/d/optout.
