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 <echar...@american.edu> On Mon, Jul 4, 2016 at 5:13 PM, Barry MacKichan < barry.mackic...@mackichan.com> 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
