On 23 August 2018 at 06:31, <[email protected]> wrote: > > > On Thursday, August 23, 2018 at 2:01:24 AM UTC, Jason wrote: >> >> >> >> On Wed, Aug 22, 2018 at 4:43 PM <[email protected]> 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
It is not true that all well-defined functions are computable. You have already been given examples by Jason and John of well-defined mathematical functions that are non-computable. You seem to confuse "well-defined" with "written in closed form". The latter is not even well-defined (heheh) because it hangs on the idea of a set of "well-known" functions, and people already have different ideas on what that set includes. Having well-known representations such as sin(x) or e^x, or even x + y does not magically make the related computations non-algorithmic. How do you think you learned how to add, subtract, multiply and divide in basic school? Those were algorithms. Well-defined just means that there is a non-ambiguous way to know if a given value corresponds to a given input of the function. If I tell you to consider the function f, such that its value is zero no matter the input, then I gave you a well-defined function in plain English. There is nothing magical about notation. Telmo. > -- > 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. -- 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.
