Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Newsgroups | sci.logic |
| Subject | Re: Infinitely Recursive input on HP Proofs |
| Date | 2018-01-22 02:40 +0000 |
| Organization | A noiseless patient Spider |
| Message-ID | <877esawr8u.fsf@bsb.me.uk> (permalink) |
| References | (9 earlier) <9c66444f-a6e3-430b-9e92-152080000df2@googlegroups.com> <87607y3bgu.fsf@bsb.me.uk> <1feee1c9-ed5f-49b1-a385-eadff3fa11be@googlegroups.com> <874lnh1js3.fsf@bsb.me.uk> <06a52a41-1cf3-447c-a983-7cfd89cc589f@googlegroups.com> |
peteolcott <peterolcott2@gmail.com> writes:
> On Friday, January 19, 2018 at 6:00:47 PM UTC-6, Ben Bacarisse wrote:
>> peteolcott writes:
>>
>> > On Thursday, January 18, 2018 at 7:04:52 PM UTC-6, Ben Bacarisse wrote:
>> >> peteolcott writes:
>> >>
>> >> > On Tuesday, January 16, 2018 at 7:09:26 PM UTC-6, Ben Bacarisse wrote:
>> >> >> George Greene writes:
>> >> >> <snip>
>> >> >> > The ACTUAL correction would read something like
>> >> >> > qx Wm Wm ⊢* Ĥ y1 qn y2 ,
>> >> >> > since Linz's notation ALWAYS starts with the state where you are beginning.
>> >> >> > You are just assuming continuation from the previous/last state,
>> >> >> > which is correct, but again, the question is HOW TO WRITE it clearly,
>> >> >> > and Linz just fails massively.
>> >> >>
>> >> >> Linz has a notation that could have been used to clear this up but it's
>> >> >> even more cumbersome: q_(A,0) for state 0 of machine A. And while it
>> >> >> makes it clear what states belong to which machine that also obscures
>> >> >> the fact the all the machines in the construction share a lot of states
>> >> >> and transitions. Do you say that q_(H,i) = q_(H',i) for all n states of
>> >> >> H,
>> >> >
>> >> > That would be a neat trick since H and H' have mutually exclusive
>> >> > states.
>> >>
>> >> No, H and H' may have non-intersecting state sets or they may not have.
>> >
>> > If a cat is defined to be an animal you are no longer free to define
>> > a cat as a pile of bricks. H is defined with two final states, H' is and
>> > adapted form of H where one of these final states has been converted
>> > into an infinite loop.
>> >
>> >> You can define H' either way. The fact that you can't see this is very
>> >> telling.
>> >>
>> > That is analogous to defining a cat as a pile of bricks, thus
>> > positing this absurdity you are showing your lack of integrity.
>>
>> No. You analogy reveals you don't understand either what I wrote or
>> what a TM is. Important facts about cats (such as they are not dogs) do
>> not depend on the names given to their hairs.
>>
>> >> The states themselves have almost no significance for TMs. What matters
>> >> is the state transition function.
>> >
>> > state ((qy)) that was converted to (qy) ∞, both transitions
>> > having a defined semantics, equivalent to Boolean True.
>>
>> No again. The states have no semantics of any significance. We can call
>> them the green and the purple states. The theorem then tells us of the
>> non-existence of a TM that can decide which strings encode those TMs
>> that enter a purple state (or, for that matter, a green state).
>>
>
> Definition 3.1 page 128, Sipster 1997
> 1. Q is the set of states,
> 2. ∑ is the input alphabet, not containing the special blank symbol ◻,
> 3. Γ is the tape alphabet, where {◻} ∈ Γ and ∑ ⊆ Γ,
> 4. δ: Q x Γ → Q x Γ x {L, R} is the transition function,
> 5. q0 ∈ Q is the start state,
> 6. qaccept ∈ Q is the accept state, and
> 7. qreject ∈ Q is the reject state, where qreject ≠ qaccept.
>
> The last two are semantics of significance.
No. Here's my definition of a Ben Machine: (Q, S, G, d, q0, pp, qg).
Q is the set of states. S and G are the input and tape alphabet (with
space in G, space not in S and S a subset of G). d is the state
transition function (Q x G -> Q x G x {L,R}). q0 is the start state, qp
is the purple state and qg is the green state (q0, qp, qg all in Q with
pq =/= pg). Just as above, execution stops on entering either the
purple or the green state.
Now it's possible that, according to you, Ben machines have no
semantics. Are you therefore happy to accept the halting theorems for
Ben machines? I say theorems plural because there are two forms of it.
One states that there is no BM which enters the purple state if and only
if the input encodes a (BM,input) pair for a halting computation. The
other says that there is no BM which enters the green state if, and only
if, the input encodes a (BM,input) pair for a halting computation.
And I can keep going... Consider NTBM's (non-terminating Ben machines)
whose state transition functions are total (the always do something) and
which have *no halting states at all*. Instead, in addition to an
initial state there is a nominated yellow state which, apart form being
singled out as the yellow state, is the same as all the others.
NTBM's have no hating theorem, of course, because none of them halt.
But here is a theorem about them: there is no NTBM that enters its
yellow state at least once if, and only if, the input tape encodes a
(NTBM,input) pair representing a NTBM which would enter its yellow state
at least once when presented with "input" as it's initial tape.
Do you accept that this is a theorem? Do these machine and/or this
theorem have "semantics"? Can you see any connection to Turing's
theorem and/or Rice's theorem?
--
Ben.
Back to sci.logic | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-16 13:25 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-16 14:09 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-17 20:05 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-17 20:28 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-17 21:09 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-17 21:15 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-18 09:37 +0000
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-18 10:50 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-18 07:57 -0800
Re: Infinitely Recursive input on HP Proofs Peter Percival <peterxpercival@hotmail.com> - 2018-01-18 16:28 +0000
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-18 10:22 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-18 10:30 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-18 10:51 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-17 01:09 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-18 08:18 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-18 10:01 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-18 10:22 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-21 20:58 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-22 15:45 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-22 18:18 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-19 01:04 +0000
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-18 17:54 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-18 19:12 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-18 19:32 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-18 20:06 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-18 20:20 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-18 21:10 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-20 00:06 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-18 19:36 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-18 18:50 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-18 19:38 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-20 00:00 +0000
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-20 00:12 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-21 07:19 -0800
Re: Infinitely Recursive input on HP Proofs Jim Burns <james.g.burns@att.net> - 2018-01-21 21:32 -0500
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-22 15:22 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-22 17:31 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-22 02:40 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-22 14:59 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-23 01:58 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-22 18:17 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-22 18:34 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-22 19:02 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-22 21:30 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-22 21:35 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-23 11:43 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-23 08:31 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-23 20:30 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-23 14:11 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-24 01:20 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-23 17:56 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-25 02:04 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-24 18:14 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-25 02:38 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-24 18:48 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-25 04:07 +0000
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-23 22:05 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-23 22:16 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-24 19:43 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-24 20:17 -0800
Re: Infinitely Recursive input on HP Proofs grahamcooper7@gmail.com - 2018-01-24 20:57 -0800
Re: Infinitely Recursive input on HP Proofs grahamcooper7@gmail.com - 2018-01-24 21:00 -0800
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-25 11:31 +0000
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-25 07:28 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-23 22:09 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-23 22:27 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-24 19:48 -0800
Re: Infinitely Recursive input on HP Proofs Peter Percival <peterxpercival@hotmail.com> - 2018-01-21 17:41 +0000
Re: Infinitely Recursive input on HP Proofs Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-01-22 01:18 +0000
Re: Infinitely Recursive input on HP Proofs Peter Percival <peterxpercival@hotmail.com> - 2018-01-22 12:38 +0000
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-21 20:49 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-21 20:51 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-22 15:24 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-22 17:32 -0800
Re: Infinitely Recursive input on HP Proofs Mikko <mikko.levanto@outlook.com> - 2018-01-23 20:15 +0200
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-23 14:13 -0800
Re: Infinitely Recursive input on HP Proofs peteolcott <peterolcott2@gmail.com> - 2018-01-22 15:40 -0800
Re: Infinitely Recursive input on HP Proofs George Greene <greeneg@email.unc.edu> - 2018-01-22 18:10 -0800
csiph-web