> On 24 Aug 2018, at 14:24, Telmo Menezes <[email protected]> wrote: > > 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. >
In fact, I will show that basically every attribute on programs, which we can defined easily with precision, are NOT computable. For example “being the code of a program computing the addition function” will be proved to be NOT computable. Of course, being the code of a halting program, is also not computable, or being the code of a total function (total means defined on all its possible inputs), etc. Being the code of a total computable function is the first thing that we will see to be not computable. I will do that today, … so everyone has a bit of more time to make the exercise on the combinators, but as promised I will give the solution too (perhaps Monday). Bruno > 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. -- 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.
