Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Newsgroups | comp.theory |
| Subject | Re: Infinitely Recursive input on HP Proofs |
| Date | 2017-03-18 01:39 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <8737ebs6rn.fsf@bsb.me.uk> (permalink) |
| References | (6 earlier) <14f8455e-9cce-4b58-b719-4541ce1633ea@googlegroups.com> <87a88ltit4.fsf@bsb.me.uk> <d86231f1-d62e-4ab5-be36-889e0f5e41b5@googlegroups.com> <87shmcsx9t.fsf@bsb.me.uk> <e4b3e5cb-a327-497d-bc2e-4279f7c36662@googlegroups.com> |
peteolcott <peterolcott2@gmail.com> writes: > On Thursday, March 16, 2017 at 4:54:25 PM UTC-5, Ben Bacarisse wrote: >> peteolcott <peterolcott> writes: >> >> > On Thursday, March 16, 2017 at 9:09:16 AM UTC-5, Ben Bacarisse wrote: >> >> peteolcott <peteolcott> writes: >> >> >> >> > On Wednesday, March 15, 2017 at 3:40:05 PM UTC-5, Ben Bacarisse wrote: >> >> >> peteolcott <peteolcott> writes: >> >> <snip> >> >> >> > // Corrected H^ source from page 319 >> >> >> > q0 Wm |-* H^ qx Wm Wm |-* H^ ∞ >> >> >> > q0 Wm |-* H^ qx Wm Wm |-* H^ y1 qn y2 >> >> >> >> >> >> That's not a correction unless you explain what qx is. Here, I actually >> >> >> agree with you -- his notation does not capture what the text says. You >> >> >> should say what qx is and how that makes the argument watertight. Can >> >> >> you do that? >> >> > >> >> > qx is merely an arbitrary state immediately after H^ has copied its >> >> > input. The text says that H^ returns to its own start state q0 which >> >> > would have H^ stuck in infinite loop of only copying its input. >> >> >> >> Yes, but qx is not at all arbitrary. For H^ to behave like H', qx must >> >> be the initial sate of H' (which is the initial state of H). >> >> >> >> Personally, I would define H^ to have an initial state q0^ (the first of >> >> the few extra states needed for the copying TM). That way, q0 remains >> >> the name of the initial state of H' and H enabling one to write >> >> >> >> q0^ Wm |-*H^ q0 Wm Wm >> >> >> >> Anyway, I am glad that you now see that H^ does not loop endlessly >> >> copying its input. >> > >> > You did not notice that the author quit talking about H' >> >> Who is "the author"? I (the author here) wanted to explain something to >> you (well, anyone who might read the post) and that requires that I talk >> about H'. >> > > If I am talking about what Linz is saying about H^. H' changes the > subject of my execution trace of H^. First not sentence. Second not answer my question. > An ordinary purely sequential execution trace of H^ on its input would > never reach the H' infinite loop. If H^ was analyzing what its input > does entirely on the basis of executing its input in sequential order, > then H^ would be stuck in infinite recursion and never make it to its > own ((y)) or ((n)) states. > > You have to really pay very close attention to see this. I So long as you know what you mean by all that, there's no need for me to comment on it. >> <snip> >> > This minor error on the Linz's part is easily corrected: >> > ---q0 Wm |-* H^ qx Wm Wm |-* H^ ∞ >> > ---q0 Wm |-* H^ qx Wm Wm |-* H^ y1 qn y2 >> > Where qx is defined as the state immediately after the input has been >> > copied. >> >> Yes, specifically, the initial state of H (and H' since they can be seen >> as having the same start state). As I explained above, it's simpler to >> introduce a new name (q0^) for the initial state of H^ so you can write > > No, No, No No. When H' is created from H its modifications create > entirely new source-code. TMs have no source code. By all means think of each derived machine as having new states but you still have to find some way to relate them. You need to say that qx is the initial state of H or H' or your notation means nothing. > That they have things in common with the original, source code is > irrelevant. What an extraordinary remark. That the machines H, H' and H^ have things in common is exactly the crux of the argument. > The convention is that every finite state machine always begins in its > own start state of 0. Zero is used because zero is an integer index > into a state transition matrix. > > Textbooks never ever use different naming conventions for the start > state different finite state machines. You don't strike me as conventional, but one way or another you need to explain what the states in your line are. You can't use q0 for the start state of H^ and for the start state of what was H' but is now incorporated into H^. I've offered my clarification but you have not given your alternative. >> q0^ Wm |-* H^ q0 Wm Wm |-* H^ ∞ >> q0^ Wm |-* H^ q0 Wm Wm |-* H^ y1 qn y2 >> >> It's obviously better to give new names to new states and keep the old >> names for the old ones. Introducing a new name (qx) for an old state >> (q0 of H) just complicates matters. > > The first q0 is the start state of H^. the second q0 is also the start > state of H^ yet H^ is not in its start state anymore because it has > just copied its input. The second q0 refers to H^ and says that it has > not copied its input yet. > > The second q0 is the H^ state after it has copied its input, call it > qc for copied input. Linz already has qy for Yes and qn for no. I think you see the problem but you are not offering any better solution. If you don't like mine, you need to come up with your own. >> So, do you now understand Linz's proof? You can't think that H^ copies >> the tape endlessly anymore, so is there any other point that you are >> having trouble with? >> >> -- >> Ben. > > His source code does indicate the H^ does copy its own endlessly in an > infinite loop. Since his intention was to show the Halting Problem > then this aspect is a mistake on the part of Linz. Yes, it is but are you able to understand the proof now? The text makes it clear so you might have been able to follow the proof despite this detail. I can always have another go at explaining it if you like. > q0 Wm |-* H^ qc Wm Wm |-* H^ ∞ > q0 Wm |-* H^ qc Wm Wm |-* H^ y1 qn y2 > > Now with this corrected source code (unless H^ is smart) it is stuck > in infinite recursion copying its input. That's neither source code nor a correction. I'm wondering if you even know what this notation that Linz uses means. I explained how to correct it, but since you've rejected my correction, you need to come up with your own. > If we assume the simplest possible case where H^ attempts to be a halt > decider by simply executing every step of its input we see that this > creates an infinite sequence of copies that each never reach their own > q((y)) or q((n)) states. Yes, because there is an error in the notation. You should know enough by now to be able to correct the error, but I don't think you know what the notation means. An error in a proof does not make the theorem incorrect. In this case it's trivial to correct this error -- you just need to make the notation reflect the what text describes. Can you do that? <snip> -- Ben.
Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Infinitely Recursive input on HP Proofs peteolcott <peteolcott@gmail.com> - 2017-03-11 13:13 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-12 11:25 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peteolcott@gmail.com> - 2017-03-12 10:58 -0700
Re: Infinitely Recursive input on HP Proofs Kaz Kylheku <336-986-7787@kylheku.com> - 2017-03-12 19:34 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peteolcott@gmail.com> - 2017-03-13 07:23 -0700
Re: Infinitely Recursive input on HP Proofs peteolcott <peteolcott@gmail.com> - 2017-03-15 08:46 -0700
Re: Infinitely Recursive input on HP Proofs peteolcott <peteolcott@gmail.com> - 2017-03-15 12:17 -0700
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-15 20:40 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peteolcott@gmail.com> - 2017-03-15 14:01 -0700
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-16 14:09 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2017-03-16 09:53 -0700
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-16 21:54 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2017-03-17 07:09 -0700
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-18 01:39 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2017-03-18 05:40 -0700
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-18 15:35 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2017-03-18 12:52 -0700
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-18 21:35 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2017-03-20 07:16 -0700
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-20 18:07 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2017-03-21 05:03 -0700
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-21 19:47 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2017-03-22 05:35 -0700
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-22 16:41 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2017-03-23 06:24 -0700
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-25 01:11 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2017-03-25 08:09 -0700
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-25 21:58 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2017-03-27 06:18 -0700
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-27 22:20 +0100
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2017-03-28 15:33 -0700
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-29 01:29 +0100
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2017-03-25 19:57 -0700
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-26 23:53 +0100
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-13 03:14 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peteolcott@gmail.com> - 2017-03-13 07:23 -0700
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-15 17:12 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peteolcott@gmail.com> - 2017-03-15 13:56 -0700
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-16 03:23 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peteolcott@gmail.com> - 2017-03-15 21:22 -0700
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-16 10:19 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2017-03-16 09:26 -0700
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-16 22:00 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2017-03-17 07:17 -0700
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2017-03-28 10:20 -0700
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-29 01:18 +0100
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2017-03-29 10:09 -0700
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-04-01 02:55 +0100
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2017-04-01 05:30 -0700
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-04-02 00:50 +0100
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2017-04-01 19:10 -0700
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-04-02 03:19 +0100
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2017-04-03 06:28 -0700
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-04-04 01:27 +0100
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2017-04-09 21:41 -0700
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-04-10 14:35 +0100
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2017-04-10 13:58 -0700
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-04-11 00:58 +0100
Re: Infinitely Recursive input on HP Proofs Pete Olcott <Pete@NoEmail.address> - 2017-04-10 20:29 -0500
Re: Infinitely Recursive input on HP Proofs peteolcott <Pete@NoEmail.address> - 2017-04-29 14:29 -0500
Re: Infinitely Recursive input on HP Proofs peteolcott <Pete@NoEmail.address> - 2017-04-29 14:45 -0500
Re: Infinitely Recursive input on HP Proofs peteolcott <Pete@NoEmail.address> - 2017-04-30 13:23 -0500
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-04-30 23:05 +0100
Re: Infinitely Recursive input on HP Proofs peteolcott <Pete@NoEmail.address> - 2017-04-30 18:43 -0500
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-05-01 13:45 +0100
Re: Infinitely Recursive input on HP Proofs peteolcott <Pete@NoEmail.address> - 2017-04-30 13:24 -0500
Re: Infinitely Recursive input on HP Proofs Peter Percival <peterxpercival@hotmail.com> - 2017-04-27 21:16 +0100
Re: Infinitely Recursive input on HP Proofs Pete Olcott <Pete@NoEmail.address> - 2018-01-26 11:37 -0600
Re: Infinitely Recursive input on HP Proofs Pete Olcott <Pete@NoEmail.address> - 2018-01-31 00:14 -0600
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-31 21:57 +0000
Re: Infinitely Recursive input on HP Proofs Pete Olcott <Pete@NoEmail.address> - 2018-01-31 19:10 -0600
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-01 01:51 +0000
Re: Infinitely Recursive input on HP Proofs Pete Olcott <Pete@NoEmail.address> - 2018-02-03 00:38 -0600
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-03 13:37 +0000
Re: Infinitely Recursive input on HP Proofs Pete Olcott <Pete@NoEmail.address> - 2018-02-03 14:27 -0600
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-03 23:49 +0000
Re: Infinitely Recursive input on HP Proofs Pete Olcott <Pete@NoEmail.address> - 2018-01-31 19:27 -0600
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-01 02:13 +0000
Re: Infinitely Recursive input on HP Proofs Pete Olcott <Pete@NoEmail.address> - 2018-02-01 21:15 -0600
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-02 21:13 +0000
Re: Infinitely Recursive input on HP Proofs Peter Percival <peterxpercival@hotmail.com> - 2018-02-02 21:30 +0000
Re: Infinitely Recursive input on HP Proofs Andy Walker <anw@cuboid.co.uk> - 2018-02-03 18:17 +0000
Re: Infinitely Recursive input on HP Proofs Andy Walker <anw@cuboid.co.uk> - 2018-02-03 18:42 +0000
Re: Infinitely Recursive input on HP Proofs Pete Olcott <Pete@NoEmail.address> - 2018-02-08 18:44 -0600
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-09 11:08 +0000
Re: Infinitely Recursive input on HP Proofs Peter Percival <peterxpercival@hotmail.com> - 2018-02-11 17:55 +0000
Re: Infinitely Recursive input on HP Proofs Pete Olcott <Pete@NoEmail.address> - 2018-02-12 20:39 -0600
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2017-03-25 19:56 -0700
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Pete Olcott <Pete@NoEmail.address> - 2018-02-13 00:18 -0600
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-13 13:06 +0000
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Pete Olcott <Pete@NoEmail.address> - 2018-02-13 16:55 -0600
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-14 00:30 +0000
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Pete Olcott <Pete@NoEmail.address> - 2018-02-13 19:38 -0600
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-14 02:27 +0000
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Andy Walker <anw@cuboid.co.uk> - 2018-02-14 22:55 +0000
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Pete Olcott <Pete@NoEmail.address> - 2018-02-14 17:22 -0600
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Pete Olcott <Pete@NoEmail.address> - 2018-02-14 21:00 -0600
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-15 21:38 +0000
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Pete Olcott <Pete@NoEmail.address> - 2018-02-15 17:27 -0600
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Pete Olcott <Pete@NoEmail.address> - 2018-02-15 17:34 -0600
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-16 00:15 +0000
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Pete Olcott <Pete@NoEmail.address> - 2018-02-15 18:43 -0600
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-16 01:05 +0000
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Pete Olcott <Pete@NoEmail.address> - 2018-02-15 19:37 -0600
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-16 02:34 +0000
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Pete Olcott <Pete@NoEmail.address> - 2018-02-15 20:51 -0600
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-16 03:32 +0000
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Pete Olcott <Pete@NoEmail.address> - 2018-02-15 22:42 -0600
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-16 12:06 +0000
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Pete Olcott <Pete@NoEmail.address> - 2018-02-16 10:26 -0600
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-16 20:42 +0000
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Pete Olcott <Pete@NoEmail.address> - 2018-02-16 17:48 -0600
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-17 01:33 +0000
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-19 15:48 +0000
Re: Infinitely Recursive input on HP Proofs (Final Solution?) David Kleinecke <dkleinecke@gmail.com> - 2018-02-22 12:40 -0800
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Pete Olcott <Pete@NoEmail.address> - 2018-02-22 15:31 -0600
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Andy Walker <anw@cuboid.co.uk> - 2018-02-15 12:24 +0000
Re: Infinitely Recursive input on HP Proofs (Final Solution?) Pete Olcott <Pete@NoEmail.address> - 2018-02-15 12:25 -0600
csiph-web