Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.theory > #11910 > unrolled thread

Infinitely Recursive input on HP Proofs

Started bypeteolcott <peteolcott@gmail.com>
First post2017-03-11 13:13 -0800
Last post2018-02-15 12:25 -0600
Articles 20 on this page of 118 — 9 participants

Back to article view | Back to comp.theory


Contents

  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

Page 1 of 6  [1] 2 3 4 5 6  Next page →


#11910 — Infinitely Recursive input on HP Proofs

Frompeteolcott <peteolcott@gmail.com>
Date2017-03-11 13:13 -0800
SubjectInfinitely Recursive input on HP Proofs
Message-ID<918df253-d4f0-4370-8f73-88e6690380a1@googlegroups.com>
http://LiarParadox.org/HP_Infinite_Recursion.pdf 

As this page 319 of An Introduction to Formal Languages and Automata
by Peter Linz 1990 indicates

From H' we construct another Turing machine H-Hat. This new machine takes as input Wm, copies it then behaves exactly like H'.
 
q0 Wm |-* H-Hat q0 Wm Wm...

Page 320 indicates that we apply H-Hat to itself as input.

The problem is that every H-Hat needs a pair of inputs.

H-Hat takes an H-Hat as input and copies it so that it 
can analyze how its input H-hat would analyze the copy
of H-Hat that it just made. 

The input H-Hat would have to copy its own input H-Hat 
so that it can analyze what its own input H-Hat would 
do on its own input, on and on forever...

Copyright 2016 and 2017 Pete Olcott. 

[toc] | [next] | [standalone]


#11913

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2017-03-12 11:25 +0000
Message-ID<87o9x6wxby.fsf@bsb.me.uk>
In reply to#11910
peteolcott <peteolcott@gmail.com> writes:

> http://LiarParadox.org/HP_Infinite_Recursion.pdf 
>
> As this page 319 of An Introduction to Formal Languages and Automata
> by Peter Linz 1990 indicates
>
> From H' we construct another Turing machine H-Hat. This new machine
> takes as input Wm, copies it then behaves exactly like H'.
>  
> q0 Wm |-* H-Hat q0 Wm Wm...
>
> Page 320 indicates that we apply H-Hat to itself as input.

No, it shows H^ acting on w^ which is the representation of H^ in
{0,1}*.

> The problem is that every H-Hat needs a pair of inputs.

No.  H^ needs nothing.  Like any TM, it acts on a tape and has no
needs.

> H-Hat takes an H-Hat as input

No "an" H^.  It takes *the* representation of H^ as input...

> and copies it so that it 
> can analyze how its input H-hat would analyze the copy
> of H-Hat that it just made.

No, it copies it.  It does this for no purpose at all.  It might analyze
the input or it may not.  It might take the square root of the input, or
it might immediately halt.  H^ is simply H with an initial step.  H is
arbitrary.  For every possible Turing machine M, M^ can be constructed.

> The input H-Hat would have to copy its own input H-Hat 
> so that it can analyze what its own input H-Hat would 
> do on its own input, on and on forever...

You write as H^ has some "intent" where in fact H^ just copies the input
but is otherwise the same as H.  If your humanising metaphors about what
H^ "would have" to do is intended to explain why, in your mind, no H
satisfying the requirements that were put on it can exist, then OK, but
I doubt your explanation will help anyone else to understand the proof.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#11914

Frompeteolcott <peteolcott@gmail.com>
Date2017-03-12 10:58 -0700
Message-ID<b8772923-abef-498c-85a0-ab6723c9e6e0@googlegroups.com>
In reply to#11913
On Sunday, March 12, 2017 at 6:25:55 AM UTC-5, Ben Bacarisse wrote:
> peteolcott <peteolcott> writes:
> 
> > http://LiarParadox.org/HP_Infinite_Recursion.pdf 
> >
> > As this page 319 of An Introduction to Formal Languages and Automata
> > by Peter Linz 1990 indicates
> >
> > From H' we construct another Turing machine H-Hat. This new machine
> > takes as input Wm, copies it then behaves exactly like H'.
> >  
> > q0 Wm |-* H-Hat q0 Wm Wm...
> >
> > Page 320 indicates that we apply H-Hat to itself as input.
> 
> No, it shows H^ acting on w^ which is the representation of H^ in
> {0,1}*.
> 
> > The problem is that every H-Hat needs a pair of inputs.
> 
> No.  H^ needs nothing.  Like any TM, it acts on a tape and has no
> needs.
> 
> > H-Hat takes an H-Hat as input
> 
> No "an" H^.  It takes *the* representation of H^ as input...
> 
> > and copies it so that it 
> > can analyze how its input H-hat would analyze the copy
> > of H-Hat that it just made.
> 
> No, it copies it.  It does this for no purpose at all.  It might analyze
> the input or it may not.  It might take the square root of the input, or
> it might immediately halt.  H^ is simply H with an initial step.  H is
> arbitrary.  For every possible Turing machine M, M^ can be constructed.
> 
> > The input H-Hat would have to copy its own input H-Hat 
> > so that it can analyze what its own input H-Hat would 
> > do on its own input, on and on forever...
> 
> You write as H^ has some "intent" where in fact H^ just copies the input
> but is otherwise the same as H.  If your humanising metaphors about what
> H^ "would have" to do is intended to explain why, in your mind, no H
> satisfying the requirements that were put on it can exist, then OK, but
> I doubt your explanation will help anyone else to understand the proof.
> 
> <snip>
> -- 
> Ben.

The key thing to remember is that every instance of H-Hat must 
have its own input H-Hat which it copies so that it can evaluate 
the execution trace of its input H-Hat on this input H-Hat's 
(copy of itself) input H-Hat. This creates an infinite sequence
of copies of H-Hat. 

The above can be verified by an execution trace of the following 
source code: q0 Wm |-* H-Hat q0 Wm Wm...

H-Hat begins at its start state q0 its with Wm (TMD of H-Hat) 
input then |-* through a sequence of steps H-Hat copies its 
input and and begins evaluating its input pair: Wm Wm at the 
start state q0 of its input Wm (TMD of H-Hat) on its own input
the copied Wm (TMD of H-Hat). 

The execution trace of the initial input Wm (TMD of H-Hat)
shows that it must proceed through the same steps listed
above with its input (the TMD of H-Hat copy of itself). 
So it must make a copy of its own input so that the copy
of itself has input. This makes a new copy not shown above. 

The execution trace of the initial input Wm (TMD of H-Hat)
copy of itself must also proceed through these same steps
on the copy of itself (copy of a copy) that the original 
input Wm (TMD of H-Hat) had to perform. This adds one more
copy not shown above. 

This goes on and one forever...

So the error of the Halting Problem, is identical in following cases: 
(1) Truth Teller Paradox: x = "hasProperty(True(x))" 
(2) Liar Paradox:   x = "hasProperty(~True(x))" 
(3) Incompleteness Theorem:  G = "~(∃x) Dem(x, G)" // ** see below

The error is the because of the infinitely recursive structure 
of the above problems the evaluation of the above finite strings 
never completes. 

The infinitely recursive structure of the above finite strings
can be unequivocally shown in my own Minimal Theory of Types (MToT). 
This theory utterly eliminates all (Fred Brooks) inessential 
complexity and it thus minimal in the absolute sense of the word. 

** Derivation of simplified Incompleteness Theorem

Gödel's Proof by Nagel, Newman and Hofstadter 2001 edition
 
http://lipn.univ-paris13.fr/~duchamp/Books&more/Hofstadter/%5BErnest_Nagel,_James_R._Newman,_Douglas_R._Hofstad(BookFi.org).pdf

Pages 96 direct quote: 
~(∃x) Dem(x, Sub(y, 17, y)) 

// Page 98 direct quote
we started with the formula having Gödel number
n; then we replaced all copies of ‘y’ in it by copies of
the numeral for n. And so, sub (n, 17, n) is the Gödel
number of G.

Pages 96-98 explained more clearly as: 
n = Godel_Number("~(∃x) Dem(x, Sub(y, 17, y))") // Page 96 
G = Sub(n, 17, n) // Page 98

After substitution
G is the Gödel number of this finite string: "~(∃x) Dem(x, G)"

Copyright Pete Olcott 2016, 2017  

[toc] | [prev] | [next] | [standalone]


#11915

FromKaz Kylheku <336-986-7787@kylheku.com>
Date2017-03-12 19:34 +0000
Message-ID<20170312122957.499@kylheku.com>
In reply to#11914
On 2017-03-12, peteolcott <peteolcott@gmail.com> wrote:
> The key thing to remember is that every instance of H-Hat must 
> have its own input H-Hat which it copies so that it can evaluate 

The key thing is that Turing Machines do not have input. They have an
initial configuration, from which new states unfold according to the
machine rules.

What we understand as "input" is folded into the initial configuration.

If a computational function is modeled in terms of the Turing machine
concept, what happens is that for each possible input to the function,
we have a different Turing machine.

[toc] | [prev] | [next] | [standalone]


#11918

Frompeteolcott <peteolcott@gmail.com>
Date2017-03-13 07:23 -0700
Message-ID<0b59aefb-3279-4932-b9d2-c563ed88ff4d@googlegroups.com>
In reply to#11915
On Sunday, March 12, 2017 at 2:34:55 PM UTC-5, Kaz Kylheku wrote:
> On 2017-03-12, peteolcott <peteolcott> wrote:
> > The key thing to remember is that every instance of H-Hat must 
> > have its own input H-Hat which it copies so that it can evaluate 
> 
> The key thing is that Turing Machines do not have input. They have an
> initial configuration, from which new states unfold according to the
> machine rules.
> 

http://LiarParadox.org/HP_Infinite_Recursion.pdf 
Direct quote from Page 319
The input to H will be the description (encoded in some form) of M, say
WM, as well as the input w.

> What we understand as "input" is folded into the initial configuration.
> 

In any case my execution trace of this source code: q0 Wm |-* H-Hat q0 Wm Wm... definitely shows that when H-Hat evaluates its input it gets stuck 
in an infinite loop and thus never makes it to its altered final states. 

Finite strings showing the infinitely recursive error of other self reference paradoxes:  
(1) Truth Teller Paradox:           x = "hasProperty(True(x))" 
(2) Liar Paradox:                       x = "hasProperty(~True(x))" 
(3) Incompleteness Theorem:  G = "~(∃x) Dem(x, G)" 
Copyright 2016, 2017 Pete Olcott 

So now after decades of work it seems that I have finally shown exactly 
how all of these self-reference paradoxes are merely erroneous. 

> If a computational function is modeled in terms of the Turing machine
> concept, what happens is that for each possible input to the function,
> we have a different Turing machine.

[toc] | [prev] | [next] | [standalone]


#11924

Frompeteolcott <peteolcott@gmail.com>
Date2017-03-15 08:46 -0700
Message-ID<8c8b9d91-3354-42e4-8a1e-6f80e53952a5@googlegroups.com>
In reply to#11918
On Monday, March 13, 2017 at 9:23:50 AM UTC-5, peteolcott wrote:
> On Sunday, March 12, 2017 at 2:34:55 PM UTC-5, Kaz Kylheku wrote:
> > On 2017-03-12, peteolcott <peteolcott> wrote:
> > > The key thing to remember is that every instance of H-Hat must 
> > > have its own input H-Hat which it copies so that it can evaluate 
> > 
> > The key thing is that Turing Machines do not have input. They have an
> > initial configuration, from which new states unfold according to the
> > machine rules.
> > 
> 
> http://LiarParadox.org/HP_Infinite_Recursion.pdf 
> Direct quote from Page 319
> The input to H will be the description (encoded in some form) of M, say
> WM, as well as the input w.
> 
> > What we understand as "input" is folded into the initial configuration.
> > 
> 
> In any case my execution trace of this source code: q0 Wm |-* H-Hat q0 Wm Wm... definitely shows that when H-Hat evaluates its input it gets stuck 
> in an infinite loop and thus never makes it to its altered final states. 
> 
> Finite strings showing the infinitely recursive error of other self reference paradoxes:  
> (1) Truth Teller Paradox:           x = "hasProperty(True(x))" 
> (2) Liar Paradox:                       x = "hasProperty(~True(x))" 
> (3) Incompleteness Theorem:  G = "~(∃x) Dem(x, G)" 
> Copyright 2016, 2017 Pete Olcott 
> 
> So now after decades of work it seems that I have finally shown exactly 
> how all of these self-reference paradoxes are merely erroneous. 
> 
> > If a computational function is modeled in terms of the Turing machine
> > concept, what happens is that for each possible input to the function,
> > we have a different Turing machine.

Yes and following this theory that you just stated every instance of the Halting Problem specification has the same infinitely recursive evaluation sequence as the above list of three paradoxes. 

So if the Halting Problem is a math problem this would unequivocally prove its erroneous nature. Any finite string that has an infinitely long evaluation sequence is not a truth bearer / logical proposition. 

Thus when we evaluate the truth of the following:
- (1) Truth Teller Paradox:           x = "hasProperty(True(x))" 
- (2) Liar Paradox:                       x = "hasProperty(~True(x))" 
- (3) Incompleteness Theorem:  G = "~(∃x) Dem(x, G)" 

Since none of them are finite strings representing truth bearers / 
logical propositions we might have well have asked if the following 
finite string is true or false: "jf58 dg5d sdf6d  6msd"

This becomes much more obvious when I translate predicate logic 
into my Minimal Type Theory expressed as a Directed Acyclic Graph.

*** NOTE *** 
I made the claim in this forum several years ago that the erroneous nature of these paradoxes could be seen when we attempt to translate them into their Directed Acyclic Graph representation. 

It took me all of these years to sufficiently elaborate my Minimal Type Theory (MTT) so that this point could be proven. 

When we represent predicates and their arguments as nodes in a DAG:

"Seven is greater than Five."
Integer-Greater-Than(Seven, Five)
(1) Integer-Greater-Than --->(2)(3) // binary tree, thus acyclic 
(2) Seven
(3) Five

"This sentence is not true."
∃x ∈ finite strings
∃True ∈ Predicates
∃hasProperty ∈ Predicates |
x = "hasProperty(~True(x))"

(1) hasProperty ---> (2)  // Alias for x 
(2) Negation      ---> (3) 
(3) True             ---> (1)  // introduces a cycle, thus not acyclic 

G = "~(∃x) Dem(x, G)"
(1) Negation      ---> (2)    // Alias for G
(2) There-Exists ---> (3)
(3) Dem             ---> (4)(1)  // introduces a cycle, thus not acyclic
(4) x

Copyright 2017 Pete Olcott

[toc] | [prev] | [next] | [standalone]


#11926

Frompeteolcott <peteolcott@gmail.com>
Date2017-03-15 12:17 -0700
Message-ID<1ffa5f15-9a4a-4ca1-bae0-a1a0addf5f5a@googlegroups.com>
In reply to#11915
On Sunday, March 12, 2017 at 2:34:55 PM UTC-5, Kaz Kylheku wrote:
> On 2017-03-12, peteolcott <peteolcott> wrote:
> > The key thing to remember is that every instance of H-Hat must 
> > have its own input H-Hat which it copies so that it can evaluate 
> 
> The key thing is that Turing Machines do not have input. They have an
> initial configuration, from which new states unfold according to the
> machine rules.
> 
> What we understand as "input" is folded into the initial configuration.
> 
> If a computational function is modeled in terms of the Turing machine
> concept, what happens is that for each possible input to the function,
> we have a different Turing machine.

Yes, I agree. That means that we are asking H^ to evaluate whether or not an infinite string representing an infinite sequence of Turing Machines halts on each of their inputs. 

This way of looking it precisely corresponds to the logical error of these: 
-> (1) Truth Teller Paradox:           x = "hasProperty(True(x))" 
-> (2) Liar Paradox:                       x = "hasProperty(~True(x))" 
-> (3) Incompleteness Theorem:  G = "~(∃x) Dem(x, G)" 

If the above strings were even syntactically correct WFF of predicate logic then they would be semantically incorrect on the basis that the evaluation of these strings is an infinite sequence. 

A formula {A} is a syntactic consequence within some 
formal system {FS} of a set {Gamma} of formulas if there 
is a formal proof in {FS} of {A} from the set {Gamma}:
∃A ∈ FS, ∃Gamma ∈ FS | (Gamma ⊢ A) 

Tarski's formal correctness of True formula: ∀x True(x) ↔ φ(x)
The following formula defines: φ(x) as (Gamma ⊢ A)  
∀A ∈ finite strings, ∃Gamma ∈ FS | (Gamma ⊢ A) ↔ True(A)

// Corrected H^ source from page 319 
q0 Wm |-* H^ qx Wm Wm |-* H^ ∞ 
q0 Wm |-* H^ qx Wm Wm |-* H^ y1 qn y2 

// Just to minimize the complexity of the analysis
// and thus provide cognitive leverage ala Fred Brooks
// elimination of inessential complexity:
// We assume that H^ is a Turing Machine Description
// that is executed within a Universal Turing Machine.

H^(Wm) ↔ H^(H^)

Halts(H^, H^) = ∃x ∈ H^ | x ⊢ H^.((qn))
~Halts(H^, H^) = ∃x ∈ H^ | x ⊢ H^.((qy))

Halts(H^, H^) is defined as: There exists a sequence of steps in H^ such that H^(H^) halts in its final state ((qn)).  

~Halts(H^, H^) is defined as: There exists a sequence of steps in H^ such that H^(H^) transitions to its state ((qy)).  

[toc] | [prev] | [next] | [standalone]


#11927

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2017-03-15 20:40 +0000
Message-ID<87wpbqtgt9.fsf@bsb.me.uk>
In reply to#11926
peteolcott <peteolcott@gmail.com> writes:
<snip>
> ... That means that we are asking H^ to evaluate whether or
> not an infinite string representing an infinite sequence of Turing
> Machines halts on each of their inputs.

No.  The only thing asked of H^ is to copy its finite input tape and
then act as H' does (H' is a machine derived from the supposed halting
decider H).

<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?

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#11929

Frompeteolcott <peteolcott@gmail.com>
Date2017-03-15 14:01 -0700
Message-ID<14f8455e-9cce-4b58-b719-4541ce1633ea@googlegroups.com>
In reply to#11927
On Wednesday, March 15, 2017 at 3:40:05 PM UTC-5, Ben Bacarisse wrote:
> peteolcott <peteolcott> writes:
> <snip>
> > ... That means that we are asking H^ to evaluate whether or
> > not an infinite string representing an infinite sequence of Turing
> > Machines halts on each of their inputs.
> 
> No.  The only thing asked of H^ is to copy its finite input tape and
> then act as H' does (H' is a machine derived from the supposed halting
> decider H).

I explain this very much more clearly in my prior post to you.
 
> 
> <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. 

> 
> <snip>
> -- 
> Ben.

[toc] | [prev] | [next] | [standalone]


#11933

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2017-03-16 14:09 +0000
Message-ID<87a88ltit4.fsf@bsb.me.uk>
In reply to#11929
peteolcott <peteolcott@gmail.com> 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.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#11935

Frompeteolcott <peterolcott2@gmail.com>
Date2017-03-16 09:53 -0700
Message-ID<d86231f1-d62e-4ab5-be36-889e0f5e41b5@googlegroups.com>
In reply to#11933
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.
> 
> -- 
> Ben.

You did not notice that the author quit talking about H'

I only have to put |--- characters in front of every line because Google would automatically hide these quotes that I already said. If you did not keep ignoring what I say this would not be necessary.

|---Direct quote of page 319
|---From H' we construct another Turing machine H^. This new machine
|---takes as input WM, copies it, and then behaves exactly like H'. 
|---Then the action of H^ is such that

|---q0 Wm |-* H^ q0 Wm Wm |-* H^ ∞ 
|---q0 Wm |-* H^ q0 Wm Wm |-* H^ y1 qn y2

|---Direct quote from page 320: 
|---Now H^ is a Turing machine, so that it will have some 
|---description in ∑*, say w^. This string, in addition to 
|---being the description of H^ can also be used as input 
|---string. We can therefore legitimately ask what would 
|---happen if H^ is applied to w^. 

Because of this mistake on your part you did not notice that
both references to the initial state q0 refer to the initial
state of H^. Thus you did not notice that the above source
code indicates that H^ is stuck in an infinite loop of copying
its input. 

Since I have two patents on finite state machines I really do 
understand how state transitions work:
US7046848B1
US9171207B1

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.

[toc] | [prev] | [next] | [standalone]


#11936

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2017-03-16 21:54 +0000
Message-ID<87shmcsx9t.fsf@bsb.me.uk>
In reply to#11935
peteolcott <peterolcott2@gmail.com> 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'.

<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

  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.

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.

[toc] | [prev] | [next] | [standalone]


#11938

Frompeteolcott <peterolcott2@gmail.com>
Date2017-03-17 07:09 -0700
Message-ID<e4b3e5cb-a327-497d-bc2e-4279f7c36662@googlegroups.com>
In reply to#11936
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^. 

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

> <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. 

That they have things in common with the original, source code is irrelevant. 

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. 

> 
>   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. 

> 
> 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. 

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. 

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. 

I know this is the case because of the 2000 hours that I spent since last June studying the Liar Paradox. Amazingly enough Gödel’s first Incompleteness Theorem  makes this same mistake: 

Only a single page of text here:
http://LiarParadox.org/Minimal_Type_Theory.pdf

[toc] | [prev] | [next] | [standalone]


#11940

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2017-03-18 01:39 +0000
Message-ID<8737ebs6rn.fsf@bsb.me.uk>
In reply to#11938
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.

[toc] | [prev] | [next] | [standalone]


#11941

Frompeteolcott <peterolcott2@gmail.com>
Date2017-03-18 05:40 -0700
Message-ID<b558a8ed-fbab-4faa-90a3-fba6e6b7442a@googlegroups.com>
In reply to#11940
On Friday, March 17, 2017 at 8:39:09 PM UTC-5, Ben Bacarisse wrote:
> peteolcott <peterolcott> 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'.
> >> 
> >
The author is Linz and he totally redefined H' which became H^, then he stopped talking about H' and only talked 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.

I am only elaborating everything that Linz is saying about how H^ is defined and how Linz described its state transition matrix. The key part is exactly what happens when H^ is applied to w^. 

> 
> > 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.
> 

I need for you to understand what I am saying. The only reason that I am talking to you is so that I can find words that are clear enough that others can understand exactly what I am saying. For many years my ideas were only stored in my mind as intuitions. Now through my Minimal Type Theory and Predicate Logic I can finally formalize these ideas. 

> >> <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.
> 

I am calling Linz's description of H^ state transition matrix source code, this would be obvious to anyone that understood state transition matrices. 
+++ q0 Wm |-* H^ qc Wm Wm |-* H^ qy ∞ 
+++ q0 Wm |-* H^ qc Wm Wm |-* H^ y1 qn y2

The last time that I told you this I did it by direct quotes that you must have ignored or I would not have to say this all again. 

I will describe it step by (I think I already did this once)
q0                    // H^ start state
Wm                  // Input to H^
|-*                     // an arbitrary number of state transitions that copy Wm
H^ qc Wm Wm // H^ has copied its input and is beginning to analyze WmWm
|-*                     // H^ make an arbitrary number of state transitions
H^                    // transitions to Infinity or qn with final tape position y2


> TMs have no source code.  

You have never heard of a Turing Machine Description TMD that is executed within a Universal Turing Machine UTM ? 
(Well now you have, and thus know what TM source code is called). 

> 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.

The whole sequence above is talking about the state transitions of H^.
The description already made that perfectly clear

> >> > ---q0 Wm |-* H^ qx Wm Wm |-* H^ ∞ 
> >> > ---q0 Wm |-* H^ qx Wm Wm |-* H^ y1 qn y2

Do you see the little H^ that comes before the qx ? What do you think that means? 

> 
> > 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.

From the bottom of the page 319 to to the top of the page 310 Linz is only talking about H^. 

Bottom of page 319
From H' we construct another Turing machine H^. 

> 
> >>   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.

Because I literally spent 2000 hours since June mathematically formalizing the notion of pathological self-reference using my own Minimal Theory of Types I understand the that this proof necessarily specified infinite recursion. 

I can now mathematically formalize the term [pathological self reference] that I brought up here years ago. 

Here it is in plain English:
Pathological self reference is self-reference such that the evaluation of an expression derives a cycle in its otherwise acyclic directed graph. I said this much years ago too. Now I actually have the Minmal Type Theory math to show it:

http://LiarParadox.org/ 

Finite string x asserts that it has the property of the negation of the Boolean value result of evaluating predicate True with itself as the only argument to True.

“This sentence is not true.”
∃x ∈ finite strings
∃True ∈ Predicates
∃hasProperty ∈ Predicates |
x = “hasProperty(~True(x))”

Minimal Type Theory expressed as Directed Graph
(1) hasProperty —> (2)    // x is an alias for this node
(2) Not              —> (3)
(3) True             —> (1)    // cycle indicates evaluation infinite loop

A formula z is a syntactic consequence within some formal system L
of a set Γ of formulas if there is a formal proof in L of z from the set Γ:
∃z ∈ L, ∃Γ ∈ L | (Γ ⊢ z)

// This formula defines the unary predicate: True(x)
True(x) ↔ ∀x ∈ finite strings, ∃Γ ∈ L | (Γ ⊢ x)

Here are the key details of Minimal Type Theory 
http://LiarParadox.org/Minimal_Type_Theory.pdf

> 
> > 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.  

The Turing Machine Description of a TM that is executed within a Universal Turing Machine IS THE SOURCE CODE OF TM. 

> 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.
> 

I totally explained it twice now. If you really think that I do not understand it and you really do understand it you would be able to point out any errors. 

> 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.

I already did that twice and explained every detail. Even though I explained every detail you continue to make vague statements that you think that I do not understand.

[toc] | [prev] | [next] | [standalone]


#11942

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2017-03-18 15:35 +0000
Message-ID<8760j6tx5x.fsf@bsb.me.uk>
In reply to#11941
peteolcott <peterolcott2@gmail.com> writes:

> On Friday, March 17, 2017 at 8:39:09 PM UTC-5, Ben Bacarisse wrote:
<snip>
> I am calling Linz's description of H^ state transition matrix source
> code, this would be obvious to anyone that understood state transition
> matrices.

Of course it's obvious -- it's just wrong.  Source code is not the right
way to refer to states and state transitions.  It's not even the right
way to refer to an encoded TM.  If you want to be understood, use the
right words.

> +++ q0 Wm |-* H^ qc Wm Wm |-* H^ qy ∞ 
> +++ q0 Wm |-* H^ qc Wm Wm |-* H^ y1 qn y2
>
> The last time that I told you this I did it by direct quotes that you
> must have ignored or I would not have to say this all again.
>
> I will describe it step by (I think I already did this once)
> q0                    // H^ start state
> Wm                  // Input to H^
> |-*                     // an arbitrary number of state transitions that copy Wm
> H^ qc Wm Wm // H^ has copied its input and is beginning to analyze WmWm

That's saying more than you know.  All you know is that H^ now "behaves
exactly like H'".  The best way to explain that is to state that qc is
the name you've given to what was the initial state of H' (and H) but
even if you don't like this formal notation, the text says it
explicitly: "After that it [H^] behaves exactly like H'".

> |-*                     // H^ make an arbitrary number of state transitions
> H^                    // transitions to Infinity or qn with final tape position y2
>

I don't know why you keep saying this.  You've renamed a state (a good
idea as I've said several times) so you should be able understand
Lintz's proof now.

It's a remarkably simple proof and it has very few steps.  I really
don't know what your problem is with it.  I can' help unless you say
what it is that is confusing you.

If you were a student of mine, I'd make it very concrete.  I'd give you
an actual machine H and ask you do write down H' and then H^.  Then I'd
ask you to run through the execution of H^.  Have you done that?  Do
think you could do that?

<snip>
>> 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.
>
> Because I literally spent 2000 hours since June mathematically
> formalizing the notion of pathological self-reference using my own
> Minimal Theory of Types I understand the that this proof necessarily
> specified infinite recursion.
>
> I can now mathematically formalize the term [pathological self
> reference] that I brought up here years ago.

But I don't care about that sort of waffle.  My concern is whether you
understand Linz's proof.  If not, would you like some help in
understanding it?

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#11943

Frompeteolcott <peterolcott2@gmail.com>
Date2017-03-18 12:52 -0700
Message-ID<8c8c186b-71e6-4f82-bd27-8390f7a6a96e@googlegroups.com>
In reply to#11942
On Saturday, March 18, 2017 at 10:35:57 AM UTC-5, Ben Bacarisse wrote:
> peteolcott <peterolcott> writes:
> 
> > On Friday, March 17, 2017 at 8:39:09 PM UTC-5, Ben Bacarisse wrote:
> <snip>
> > I am calling Linz's description of H^ state transition matrix source
> > code, this would be obvious to anyone that understood state transition
> > matrices.
> 
> Of course it's obvious -- it's just wrong.  Source code is not the right
> way to refer to states and state transitions.  It's not even the right
> way to refer to an encoded TM.  If you want to be understood, use the
> right words.

A Turing Machine Description IS the source code of a Turing Machine. 
(as George Greene of sci.logic would say: you idiot). 

> 
> > +++ q0 Wm |-* H^ qc Wm Wm |-* H^ qy ∞ 
> > +++ q0 Wm |-* H^ qc Wm Wm |-* H^ y1 qn y2
> >
> > The last time that I told you this I did it by direct quotes that you
> > must have ignored or I would not have to say this all again.
> >
> > I will describe it step by (I think I already did this once)
> > q0                    // H^ start state
> > Wm                  // Input to H^
> > |-*                     // an arbitrary number of state transitions that copy Wm
> > H^ qc Wm Wm // H^ has copied its input and is beginning to analyze WmWm
> 
> That's saying more than you know.  All you know is that H^ now "behaves
> exactly like H'".  

I call bullshit. If H^ behaved EXACTLY like H' then it would not copy its input. Try and use your words with (as much as possible) 100% perfect precision. I already called you on this before when you referred to a true opinion, (contradiction in terms). 

If you were not so sloppy in your interpretations you would have understood me years ago. 

> The best way to explain that is to state that qc is
> the name you've given to what was the initial state of H' (and H) but
> even if you don't like this formal notation, the text says it
> explicitly: "After that it [H^] behaves exactly like H'".
> 
> > |-*                     // H^ make an arbitrary number of state transitions
> > H^                    // transitions to Infinity or qn with final tape position y2
> >
> 
> I don't know why you keep saying this.  You've renamed a state (a good
> idea as I've said several times) so you should be able understand
> Lintz's proof now.
> 
> It's a remarkably simple proof and it has very few steps.  I really
> don't know what your problem is with it.  I can' help unless you say
> what it is that is confusing you.

Spend 2000 carefully going over this material again and again and NOT presuming that you already fully understand it. The biggest mistake of woefully fallible humans is that they are too damn sure of themselves. 

> 
> If you were a student of mine, I'd make it very concrete.  I'd give you
> an actual machine H and ask you do write down H' and then H^.  Then I'd
> ask you to run through the execution of H^.  Have you done that?  Do
> think you could do that?

I have two patents as sole inventor of two finite state machines what would you guess? 
US7046848B1
US9171207B1 

I was able to express their state transition matrix in a million-fold less space than is conventionally required. 

> 
> <snip>
> >> 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.
> >
> > Because I literally spent 2000 hours since June mathematically
> > formalizing the notion of pathological self-reference using my own
> > Minimal Theory of Types I understand the that this proof necessarily
> > specified infinite recursion.
> >
> > I can now mathematically formalize the term [pathological self
> > reference] that I brought up here years ago.
> 
> But I don't care about that sort of waffle.  

That formalized waffle just proved that the first Incompleteness Theorem is incorrect. 

G = "~(∃x) | (x ⊢ G)"   // Gödel’s first Incompleteness Theorem 
(1) Negation                                     ---> (2)       // G is an alias for this node
(2) Exists                                          ---> (3)(4)  
(3) x
(4) Such-That                                   ---> (5)
(5) Syntactic-Logical-Consequence ---> (3)(1)  // cycle indicates evaluation infinite loop

> My concern is whether you
> understand Linz's proof.  If not, would you like some help in
> understanding it?
> 
> <snip>
> -- 
> Ben.

[toc] | [prev] | [next] | [standalone]


#11944

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2017-03-18 21:35 +0000
Message-ID<87mvcis1xg.fsf@bsb.me.uk>
In reply to#11943
peteolcott <peterolcott2@gmail.com> writes:

> On Saturday, March 18, 2017 at 10:35:57 AM UTC-5, Ben Bacarisse wrote:
>> peteolcott <peterolcott> writes:
>> 
>> > On Friday, March 17, 2017 at 8:39:09 PM UTC-5, Ben Bacarisse wrote:
>> <snip>
>> > I am calling Linz's description of H^ state transition matrix source
>> > code, this would be obvious to anyone that understood state transition
>> > matrices.
>> 
>> Of course it's obvious -- it's just wrong.  Source code is not the right
>> way to refer to states and state transitions.  It's not even the right
>> way to refer to an encoded TM.  If you want to be understood, use the
>> right words.
>
> A Turing Machine Description IS the source code of a Turing Machine. 
> (as George Greene of sci.logic would say: you idiot). 
>
>> 
>> > +++ q0 Wm |-* H^ qc Wm Wm |-* H^ qy ∞ 
>> > +++ q0 Wm |-* H^ qc Wm Wm |-* H^ y1 qn y2
>> >
>> > The last time that I told you this I did it by direct quotes that you
>> > must have ignored or I would not have to say this all again.
>> >
>> > I will describe it step by (I think I already did this once)
>> > q0                    // H^ start state
>> > Wm                  // Input to H^
>> > |-*                     // an arbitrary number of state transitions that copy Wm
>> > H^ qc Wm Wm // H^ has copied its input and is beginning to analyze WmWm
>> 
>> That's saying more than you know.  All you know is that H^ now "behaves
>> exactly like H'".  
>
> I call bullshit.

I call not understanding.

> If H^ behaved EXACTLY like H' then it would not copy its input.

Did you miss the word "now"?

> Try
> and use your words with (as much as possible) 100% perfect
> precision. I already called you on this before when you referred to a
> true opinion, (contradiction in terms).

They are Linz's words not mine; that's why I put them in quotes.  H^
copies it's input an *then* behaves exactly like H'.  It's not hard to
understand.

Unfortunately you rejected my formal explanation using state names but
you offered not better alternative.  I see no option but to quote Linz's
words and hope that the penny drops.  You are obviously averse to asking
for help, but if you don't say what part of his proof is confusing you,
I can't help much more than that.

You can't criticise the proof until you've understood it, and you seemed
genuinely surprised ("I call bullshit") by my direct quote of Linz words
about H^ copying its input and then behaving like H'.  That suggests to
me that you don't know what Linz is saying.

<snip>
>> If you were a student of mine, I'd make it very concrete.  I'd give you
>> an actual machine H and ask you do write down H' and then H^.  Then I'd
>> ask you to run through the execution of H^.  Have you done that?  Do
>> think you could do that?
>
> I have two patents as sole inventor of two finite state machines what
> would you guess?

Since you are avoiding the question, I would guess that you think you
can't do it, but it's not hard and I'm pretty sure you could.  I'll
start you off.  Here's an example H.

  H = ({a,b}, {1,0}, {1,0,_}, d, a, _, {b})

with d(a,1) = (a,1,R), d(a,0) = (a,0,R) and d(a,_) = (b,_,L).  What are
H' and H^?

(For convenience I'm using Linz's formalism here so Q={a,b}, Sigma={1,0}
and so on.  If it's not clear, just ask.)

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#11945

Frompeteolcott <peterolcott2@gmail.com>
Date2017-03-20 07:16 -0700
Message-ID<6181c73b-b443-4df8-a371-7960809d57aa@googlegroups.com>
In reply to#11944
On Saturday, March 18, 2017 at 4:35:57 PM UTC-5, Ben Bacarisse wrote:
> peteolcott <peterolcott> writes:
> 
> > On Saturday, March 18, 2017 at 10:35:57 AM UTC-5, Ben Bacarisse wrote:
> >> peteolcott <peterolcott> writes:
> >> 
> >> > On Friday, March 17, 2017 at 8:39:09 PM UTC-5, Ben Bacarisse wrote:
> >> <snip>
> >> > I am calling Linz's description of H^ state transition matrix source
> >> > code, this would be obvious to anyone that understood state transition
> >> > matrices.
> >> 
> >> Of course it's obvious -- it's just wrong.  Source code is not the right
> >> way to refer to states and state transitions.  It's not even the right
> >> way to refer to an encoded TM.  If you want to be understood, use the
> >> right words.
> >
> > A Turing Machine Description IS the source code of a Turing Machine. 
> > (as George Greene of sci.logic would say: you idiot). 
> >
> >> 
> >> > +++ q0 Wm |-* H^ qc Wm Wm |-* H^ qy ∞ 
> >> > +++ q0 Wm |-* H^ qc Wm Wm |-* H^ y1 qn y2
> >> >
> >> > The last time that I told you this I did it by direct quotes that you
> >> > must have ignored or I would not have to say this all again.
> >> >
> >> > I will describe it step by (I think I already did this once)
> >> > q0                    // H^ start state
> >> > Wm                  // Input to H^
> >> > |-*                     // an arbitrary number of state transitions that copy Wm
> >> > H^ qc Wm Wm // H^ has copied its input and is beginning to analyze WmWm
> >> 
> >> That's saying more than you know.  All you know is that H^ now "behaves
> >> exactly like H'".  
> >
> > I call bullshit.
> 
> I call not understanding.
> 
> > If H^ behaved EXACTLY like H' then it would not copy its input.
> 
> Did you miss the word "now"?
> 
> > Try
> > and use your words with (as much as possible) 100% perfect
> > precision. I already called you on this before when you referred to a
> > true opinion, (contradiction in terms).
> 
> They are Linz's words not mine; that's why I put them in quotes.  H^
> copies it's input an *then* behaves exactly like H'.  It's not hard to
> understand.

You and Linz are both incorrect on this. If either you or Linz would have studied Linz's clearest possible specification until you grokked it you would both have the same new insight that I have. 

It is, however, so very much easier to simply understand these things in the conventional way. Also what would be your basis for even suspecting that the conventional understanding is incorrect? 

All of these years I have only had an intuition that the conventional understanding of the halting problem and the incompleteness problem are incorrect. 

My basis for this intuition it that the 2000 year old Liar Paradox
continued to lack any conventional understanding what-so-ever. Everyone knew that something was wrong yet no one knew exactly what was wrong. 

I also knew intuitively that all three of these HP, IT, and LP had pathological self reference as the source of their error. I said that here in this forum several years ago. 

It was not until about a year ago that I could state this intuition in a way that could be eventually mathematically verified. If the Incompleteness Theorem is correct then it proves that sometimes logical entailment either fails to complete or derives contradictory results. I have known that this is not possible because logical entailment is entirely based on logical tautology. 

You probably don't understand the mathematical meaning of those words and won't bother to look them up. 

This link anchors the concept of logical entailment: 
https://en.wikipedia.org/wiki/Logical_consequence#Proofs_and_models

> 
> Unfortunately you rejected my formal explanation using state names but
> you offered not better alternative.  I see no option but to quote Linz's
> words and hope that the penny drops.  You are obviously averse to asking
> for help, but if you don't say what part of his proof is confusing you,
> I can't help much more than that.

I did not reject state names. I said that Linz goofed when he resumed the execution of H^ back to its start state after it copied its input. 

> 
> You can't criticise the proof until you've understood it, and you seemed
> genuinely surprised ("I call bullshit") by my direct quote of Linz words
> about H^ copying its input and then behaving like H'.  That suggests to
> me that you don't know what Linz is saying.

No it means that I ignore some of his mistakes and correct others. Because H^ has an infinitely recursive structure and H' does not have infinitely recursive structure there is not point where H^ behaves like H'.

If we go back to the TMD of the original Turing Machine H the problem becomes simpler thus clearer: 

Page 318
Wm is a Turing Machine Description input to H
 W is input to this Turing Machine Description 

This is the Turing machine Desciption of H

q0 Wm W |-* H x1 qy x2
q0 Wm W |-* H y1 qn y2

If we run H with itself as input specified in conventional computer science functional notion we get this: H(H, H). There is no infinitely recursive structure here. Instead of infinitely recursive structure we have a third H that need an input yet has no input. 

So even the initial configuration of the hypothetical halt decider has a gap in its reasoning. Linz never specifies what a TM that requires input yet has no input does. 

For H^ he fixed this problem and has H^ copy its input before it begins its analysis. He and everyone else never pointed out that this results in an infinitely recursive problem specification. 

This may be extremely difficult for you to see, it took me 2000 hours of concentrated effort since last June to see this. Once I saw the complete formalization of this last week in the Liar Paradox and the Incompleteness Theorem, then it was easy to look for and find the same issue with the Halting Problem. 

> 
> <snip>
> >> If you were a student of mine, I'd make it very concrete.  I'd give you
> >> an actual machine H and ask you do write down H' and then H^.  Then I'd
> >> ask you to run through the execution of H^.  Have you done that?  Do
> >> think you could do that?
> >
> > I have two patents as sole inventor of two finite state machines what
> > would you guess?
> 
> Since you are avoiding the question, I would guess that you think you
> can't do it, but it's not hard and I'm pretty sure you could.  I'll
> start you off.  Here's an example H.
> 
>   H = ({a,b}, {1,0}, {1,0,_}, d, a, _, {b})
> 
> with d(a,1) = (a,1,R), d(a,0) = (a,0,R) and d(a,_) = (b,_,L).  What are
> H' and H^?
> 

Since you changed the Linz notational conventions and and did not define your differing notational conventions I have no idea what you are saying. 

> (For convenience I'm using Linz's formalism here so Q={a,b}, Sigma={1,0}
> and so on.  If it's not clear, just ask.)

That differs too much from Linz, stick with the convention of preceding every state with a q such as q0. 

This is better notation because it explicitly:
(a) Names every state in state transition order.
(b) Shows how many inputs 
(c) Shows the final tape configuration (this is not very useful)
(d) Indicates an arbitrary number of unspecified state transitions thus abstracts out unnecessary details.  

q0 Wm W |-* H x1 qy x2
q0 Wm W |-* H y1 qn y2

https://en.wikipedia.org/wiki/Formalism_(philosophy_of_mathematics) 

In foundations of mathematics, philosophy of mathematics, and philosophy of logic, formalism is a theory that holds that statements of mathematics and logic can be considered to be statements about the consequences of certain string manipulation rules.

If we assume that the input to every Turing Machine is a finite string, then we avoid any presuppositions about the nature of this finite string. Linz is assuming that some of these finite strings specify a Turing Machine Description. 

Because the Incompleteness Theorem presumes that G is a correct logical proposition it incorrectly concludes that mathematics must be either incomplete or inconsistent. It turns out that G is simply not a correct logical proposition. 

You probably won't understand any of this because it comes from mathematics and not computer science. That is OK, just don't disparage it on the basis of your lack of understanding (ignorance). 

http://lipn.univ-paris13.fr/~duchamp/Books&more/Hofstadter/%5BErnest_Nagel,_James_R._Newman,_Douglas_R._Hofstad(BookFi.org).pdf

Pages 96-97 simplified notation 
n = Gödel_Number( "~(∃x) Dem (x, Sub (y, 17, y))" )

// page 98
sub (n, 17, n) is the Gödel number of G.
G = Sub (n, 17, n)

// Thus after substitution  
G = Gödel_Number( "~(∃x) Dem (x, G)" )

// Converting to modern symbolic notation 
G = Gödel_Number( "~(∃x) | (x ⊢ G)" )

// Discarding arithmetization 
G = "~(∃x) | (x ⊢ G)"   

Minimal Type Theory (for G) expressed as Directed Graph
(1) Negation                                   ---> (2)       // G is an alias for this node
(2) Exists                                        ---> (3)(4)  
(3) x
(4) Such-That                                 ---> (5)
(5) Syntactic-Logical-Consequence ---> (3)(1)  // cycle indicates evaluation infinite loop

> 
> <snip>
> -- 
> Ben.

[toc] | [prev] | [next] | [standalone]


#11946

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2017-03-20 18:07 +0000
Message-ID<87d1dbq0so.fsf@bsb.me.uk>
In reply to#11945
peteolcott <peterolcott2@gmail.com> writes:

> On Saturday, March 18, 2017 at 4:35:57 PM UTC-5, Ben Bacarisse wrote:
>> peteolcott <peterolcott> writes:
>> 
>> > On Saturday, March 18, 2017 at 10:35:57 AM UTC-5, Ben Bacarisse wrote:
>> >> peteolcott <peterolcott> writes:
>> >> 
>> >> > On Friday, March 17, 2017 at 8:39:09 PM UTC-5, Ben Bacarisse wrote:
>> >> <snip>
>> >> > I am calling Linz's description of H^ state transition matrix source
>> >> > code, this would be obvious to anyone that understood state transition
>> >> > matrices.
>> >> 
>> >> Of course it's obvious -- it's just wrong.  Source code is not the right
>> >> way to refer to states and state transitions.  It's not even the right
>> >> way to refer to an encoded TM.  If you want to be understood, use the
>> >> right words.
>> >
>> > A Turing Machine Description IS the source code of a Turing Machine. 
>> > (as George Greene of sci.logic would say: you idiot). 
>> >
>> >> 
>> >> > +++ q0 Wm |-* H^ qc Wm Wm |-* H^ qy ∞ 
>> >> > +++ q0 Wm |-* H^ qc Wm Wm |-* H^ y1 qn y2
>> >> >
>> >> > The last time that I told you this I did it by direct quotes that you
>> >> > must have ignored or I would not have to say this all again.
>> >> >
>> >> > I will describe it step by (I think I already did this once)
>> >> > q0                    // H^ start state
>> >> > Wm                  // Input to H^
>> >> > |-*                     // an arbitrary number of state transitions that copy Wm
>> >> > H^ qc Wm Wm // H^ has copied its input and is beginning to analyze WmWm
>> >> 
>> >> That's saying more than you know.  All you know is that H^ now "behaves
>> >> exactly like H'".  
>> >
>> > I call bullshit.
>> 
>> I call not understanding.
>> 
>> > If H^ behaved EXACTLY like H' then it would not copy its input.
>> 
>> Did you miss the word "now"?
>> 
>> > Try
>> > and use your words with (as much as possible) 100% perfect
>> > precision. I already called you on this before when you referred to a
>> > true opinion, (contradiction in terms).
>> 
>> They are Linz's words not mine; that's why I put them in quotes.  H^
>> copies it's input an *then* behaves exactly like H'.  It's not hard to
>> understand.
>
> You and Linz are both incorrect on this.

Not so.  It is so by definition.

> If either you or Linz would have studied Linz's clearest possible
> specification until you grokked it you would both have the same new
> insight that I have.

There is no point in drawing silly conclusions form an error in the
text.  If you can't see past it, try any of a hundred other proofs of
this theorem.  They all use the same definition that you are denying to
Linz -- a machine copies its input and then behaves as the machine it is
derived from.

>
> It is, however, so very much easier to simply understand these things in the conventional way. Also what would be your basis for even suspecting that the conventional understanding is incorrect? 
>
> All of these years I have only had an intuition that the conventional understanding of the halting problem and the incompleteness problem are incorrect. 
>
> My basis for this intuition it that the 2000 year old Liar Paradox
> continued to lack any conventional understanding what-so-ever. Everyone knew that something was wrong yet no one knew exactly what was wrong. 
>
> I also knew intuitively that all three of these HP, IT, and LP had pathological self reference as the source of their error. I said that here in this forum several years ago. 
>
> It was not until about a year ago that I could state this intuition in a way that could be eventually mathematically verified. If the Incompleteness Theorem is correct then it proves that sometimes logical entailment either fails to complete or derives contradictory results. I have known that this is not possible because logical entailment is entirely based on logical tautology. 
>
> You probably don't understand the mathematical meaning of those words and won't bother to look them up. 
>
> This link anchors the concept of logical entailment: 
> https://en.wikipedia.org/wiki/Logical_consequence#Proofs_and_models
>
>> 
>> Unfortunately you rejected my formal explanation using state names but
>> you offered not better alternative.  I see no option but to quote Linz's
>> words and hope that the penny drops.  You are obviously averse to asking
>> for help, but if you don't say what part of his proof is confusing you,
>> I can't help much more than that.
>
> I did not reject state names. I said that Linz goofed when he resumed
> the execution of H^ back to its start state after it copied its
> input.

So fix it and more on.  None of your re-writes have been clear in how
the problem should be fixed because, of course, you don't want to fix
it.  You thought that H^ machine endlessly copied it's input and you
don't like that fact that that error is trivial to correct.  You'd be
stuck having to accept the theorem again as you did for so many years.
>
>> 
>> You can't criticise the proof until you've understood it, and you seemed
>> genuinely surprised ("I call bullshit") by my direct quote of Linz words
>> about H^ copying its input and then behaving like H'.  That suggests to
>> me that you don't know what Linz is saying.
>
> No it means that I ignore some of his mistakes and correct
> others. Because H^ has an infinitely recursive structure and H' does
> not have infinitely recursive structure there is not point where H^
> behaves like H'.

Of course you don't want to correct the poof so you pick and choose what
you call the error.  That shows only a lack of intellectual backbone.
Fix the error in the proof so the proof is correct.  Anything else is
just burying your head in the sand.

<snip>
>> >> If you were a student of mine, I'd make it very concrete.  I'd give you
>> >> an actual machine H and ask you do write down H' and then H^.  Then I'd
>> >> ask you to run through the execution of H^.  Have you done that?  Do
>> >> think you could do that?
>> >
>> > I have two patents as sole inventor of two finite state machines what
>> > would you guess?
>> 
>> Since you are avoiding the question, I would guess that you think you
>> can't do it, but it's not hard and I'm pretty sure you could.  I'll
>> start you off.  Here's an example H.
>> 
>>   H = ({a,b}, {1,0}, {1,0,_}, d, a, _, {b})
>> 
>> with d(a,1) = (a,1,R), d(a,0) = (a,0,R) and d(a,_) = (b,_,L).  What are
>> H' and H^?
>> 
>
> Since you changed the Linz notational conventions and and did not
> define your differing notational conventions I have no idea what you
> are saying.

This is Linz's notation.  You are confusing how he write execution
configurations with how he defines machines.  The explanation of the
notation for a machine is a few chapter earlier on (you have read the
book, yes?).

He defines a Turing machine an ordered 7-tuple so there can be no doubt
what H = ({a,b}, {1,0}, {1,0,_}, d, a, _, {b}) means.  All the sets and
functions are clearly specified.  Only the details of the d function
remain to written out (it would be unreadable if it were specified as a
set in the tuple) and I did that.

Anyway, as I said, I am sure that you can do this so just ask if
something is confusing you.  Which part of this machine description is
bothering you?

>> (For convenience I'm using Linz's formalism here so Q={a,b}, Sigma={1,0}
>> and so on.  If it's not clear, just ask.)
>
> That differs too much from Linz, stick with the convention of
> preceding every state with a q such as q0.

No, if you can't cope with a two-state machine with names of my choosing
you need to go back to square one.  Especially as the crucial problem
involves exactly the problem of confusing that start state of two
machines one derived from the other.  Using q0 for both is exactly the
problem you need to get round.

You sell yourself short if you think you can't cope with a machine with
two states called a and b.  I'm sure you can.

(I'm discounting the possibility that your deliberately want to use q0
for every start state so that you can try avoid correcting Linz's
mistake.  That would be disingenuous in the extreme so I will reject
that explanation for now.)

> This is better notation because it explicitly:

<re-ordered a bit: here's the notation:>

> q0 Wm W |-* H x1 qy x2
> q0 Wm W |-* H y1 qn y2
>
> (a) Names every state in state transition order.

No it doesn't.  Do you really not know what the notation means?  It's
about machine configurations.

> (b) Shows how many inputs

No it does not.  All TM's have a possibly blank tape to start with.
There is no number of inputs -- only some set of input symbols.  Again,
you seem not to know what qx a b c |-* H ... means.

> (c) Shows the final tape configuration (this is not very useful)

Actually it's crucial to the proof, but since this notation is not about
defining a machine, it does not apply here.

> (d) Indicates an arbitrary number of unspecified state transitions
> thus abstracts out unnecessary details.

Ah, yes, that would indeed help you.  What I asked for was an actual H'
and H^ derived from an actual H.  This would show that you are wrong, so
you must at all costs never do anything that clear and concrete.  Keep
it as abstract and as far away from a counterexample as possible!

Anyway, if you really think you can't write out H' and H^ from my
example H, just say so, and I'll do it for you.

<snip>
-- 
Ben.

[toc] | [prev] | [next] | [standalone]


Page 1 of 6  [1] 2 3 4 5 6  Next page →

Back to top | Article view | comp.theory


csiph-web