You can decide what it means to compute the square root of 2. For example, you can program the Turing machine to enter an accept state if it finds a number (it can) whose square is within 10^-9 of 2.
Frank Frank Wimberly Phone (505) 670-9918 On Jul 5, 2016 7:25 PM, "Nick Thompson" <[email protected]> wrote: > Thanks, Eric, > > > > That all made a lot of sense to me. Now, it may have made sense because > you are NOT, as I am not, a computer person, and therefore I understood > you. Are we about to be told we are both wrong? We’ll see. > > > > One definitional point. If one has to use an “artificial” stop rule such > as “quit when you get to the tenth decimal point”, is such a problem deemed > “computable” or “non-computable”? Can one “compute” the square root of > two? > > > > Nick > > > > Nicholas S. Thompson > > Emeritus Professor of Psychology and Biology > > Clark University > > http://home.earthlink.net/~nickthompson/naturaldesigns/ > > > > *From:* Friam [mailto:[email protected]] *On Behalf Of *Eric > Charles > *Sent:* Tuesday, July 05, 2016 2:44 PM > *To:* The Friday Morning Applied Complexity Coffee Group < > [email protected]> > *Subject:* Re: [FRIAM] Understanding you-folks > > > > Nick, > > It is not a tautology, because (at the least) it is a program written by > people, so the definition of an accept state is determined outside the > system in question. At its most basic level, the Turing machine isn't > calculating the answer to a problem, it is accepting or rejecting a > hypothesis by following a quirky set of rules. Those rules might have > you see what is written on a really long piece of paper, might have you > modify the writing that is in front of you, and might have you move > to various different spot in the really long paper (for subsequent reading > and writing). But in the end, either you reach a state where you accept the > inputs, or you reject them.... or you go on forever without an answer. (It > is interesting to figure out what problems can be solved, and how long it > can take to solve them, but the possibility of running forever is, IMHO, > what makes the whole thing so damned interesting). > > > > For example, we could write a Turing program that tells you whether one > number can be divided cleanly by another. In this case, the "accept state" > is that a sub-part of the division event occurs without remainder. That is, > if I ask (yes/no) whether you can divide 8 by 4, you will reach an accept > state and stop rather quickly. In contrast, if I ask (yes/no) whether you > can divide 8 by 9, you will go on dividing forever, never reaching an > accept state. We can get around this by adding additional rules. For > example, I might have the program give a "reject" if you get the same > numeral 5 times in a row. (Obviously, that rule won't work for all > circumstances, but it will work here.) > > > > Input -> Can you divide 8, 4? > > > > 2 > > > > Accept (i.e., the program says that you should accept that 8 is cleanly > divided by 4) > > > > ------ > > > > Input -> Can you divide 8, 9? > > > > 0 > > > > 0.8 > > > > 0.88 > > > > 0.888 > > > > 0.8888 > > > > 0.88888 > > > > Reject (i.e., the program says that you should reject that 8 is cleanly > divided by 9) > > > > ------ > > > > If we were less interested in answering the yes/no question, and more > interested in reading the output to find out what happens during the > division, then you could add an additional accept state. For example, I > might be a high school teacher who allows a rule that you can turn in an > answered rounded to the nearest hundredth. Under such a condition, there > would be two accept states: 1) You complete a division step with no > remainder. 2) You get a non-zero number in the thousandth place and round. > > > > Input -> Divide 8, 9 > > > > 0 > > > > 0.8 > > > > 0.88 > > > > 0.888 > > > > 0.89 > > > > Accept (i.e., the program says that when you divide 8 by 9 and round to > the nearest hundredth, you get to an acceptable stopping point) > > > > ----- > > > > Note that, from a theory-of-computation perspective, the latter program is > utterly uninteresting. Such a program has no risk of running forever, and > it won't ever find itself in a rejection state (assuming its inputs are two > numbers); it will always reach an "accept" state. Nevertheless, it is a > useful program to have because after the program ends up in the "accept" > state, you can read the paper and see where it was when it stopped. > > > > But always remember that the main point of cogitating > about Turing-machines isn't to imagine reading what's on the paper; the > main point is to determine what types of problems can lead to accept or > reject states, given a set of rules and some inputs (and whether they will > do so in a finite amount of time). That is, the point is to determine what > types of thing are, in principle, computable; i.e., what types of problems > can be solved using *only* methods of computation, without any leaps of > creativity, i.e., Kohler-style "insight." > > > > Best, > > Eric > > > > > > > > > > ----------- > Eric P. Charles, Ph.D. > Supervisory Survey Statistician > > U.S. Marine Corps > > > > On Mon, Jul 4, 2016 at 5:13 PM, Barry MacKichan < > [email protected]> wrote: > > That is, it’s a definition, not a theorem. > > --Barry > > > On 2 Jul 2016, at 13:06, Nick Thompson wrote: > > > I smell a tautology, here. > > ============================================================ > FRIAM Applied Complexity Group listserv > Meets Fridays 9a-11:30 at cafe at St. John's College > to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com > > > > ============================================================ > FRIAM Applied Complexity Group listserv > Meets Fridays 9a-11:30 at cafe at St. John's College > to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com >
============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College to unsubscribe http://redfish.com/mailman/listinfo/friam_redfish.com
