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


Groups > sci.logic > #172557 > unrolled thread

Re: Infinitely Recursive input on HP Proofs (Final Solution?)

Started byNewberry <newberryxy@gmail.com>
First post2018-02-12 20:27 -0800
Last post2018-02-15 12:25 -0600
Articles 20 on this page of 41 — 6 participants

Back to article view | Back to sci.logic

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.


Contents

  Re: Infinitely Recursive input on HP Proofs (Final Solution?) Newberry <newberryxy@gmail.com> - 2018-02-12 20:27 -0800
    Re: Infinitely Recursive input on HP Proofs (Final Solution?) grahamcooper7@gmail.com - 2018-02-12 21:29 -0800
    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?) peteolcott <peterolcott2@gmail.com> - 2018-02-13 20:06 -0800
          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?) grahamcooper7@gmail.com - 2018-02-14 16:20 -0800
                Re: Infinitely Recursive input on HP Proofs (Final Solution?) peteolcott <peterolcott2@gmail.com> - 2018-02-14 16:29 -0800
                  Re: Infinitely Recursive input on HP Proofs (Final Solution?) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-15 02:19 +0000
                    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?) grahamcooper7@gmail.com - 2018-02-14 22:57 -0800
                        Re: Infinitely Recursive input on HP Proofs (Final Solution?) Pete Olcott <Pete@NoEmail.address> - 2018-02-15 09:06 -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?) peteolcott <peterolcott2@gmail.com> - 2018-02-16 13:16 -0800
                                                  Re: Infinitely Recursive input on HP Proofs (Final Solution?) Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-16 23:01 +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?) grahamcooper7@gmail.com - 2018-02-16 17:49 -0800
                                                        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?) Pete Olcott <Pete@NoEmail.address> - 2018-02-22 15:31 -0600
                                        Re: Infinitely Recursive input on HP Proofs (Final Solution?) grahamcooper7@gmail.com - 2018-02-16 02:53 -0800
              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 2 of 3 — ← Prev page 1 [2] 3  Next page →


#172862

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2018-02-16 00:15 +0000
Message-ID<87sha16b84.fsf@bsb.me.uk>
In reply to#172858
Pete Olcott <Pete@NoEmail.address> writes:

> On 2/15/2018 3:38 PM, Ben Bacarisse wrote:
>> Pete Olcott <Pete@NoEmail.address> writes:
<snip>
>>> The Liar Paradox is the simplest possible example that I can provide
>>> that shows a syntactically WFF can indeed be semantically incorrect.
>>
>> It's not an example of a halting problem.  Unlike this paradox, every
>> halting problem instance has a correct yes/no answer.  You will never
>> understand any of your other errors until you accept this basic fact.
>
> This error occurs in numerous decision problems:

There are lots of errors in many decision problems, but here is no error
in the halting decision problem.

<cut stuff not about halting or TMs>

> Definition of Turing Machine Ĥx

It's /still/ not a definition of a Turning machine.  Fortunately, many
posts ago you did at least sketch the definition so I know what H^x is
supposed to be.

> Ĥx.q0 Wm ⊢* Ĥx.qx Wm Wm ⊢* Ĥx.qy
> Ĥx.q0 Wm ⊢* Ĥx.qx Wm Wm ⊢* Ĥx.qn
>
> Ĥx [Ĥx][Ĥx]

No string of the form [H^x][H^x] exists.  There are no machines that
meet the specification required of the machine H^x so there is no string
encoding of one [H^x].

> When we assume that Ĥx was constructed on the basis of a correct halt
> decider H then the above expression does represent a TMD that would halt
> on its input yet no mathematical proof from that expression to the
> semantic values of True( Halts([Ĥx][Ĥx]) ) or False( Halts([Ĥx][Ĥx]) )
> exists because the expression is semantically incorrect.

If you assume a falsehood, all sorts of problems ensue.  Endless junk
posts from you being only the tip of the iceberg.

Repeat after me: every halting problem instance has a correct yes/no
answer.  Every finite string either encodes a TM/input pair such that
the encoded TM would halt when given the encoded input, or it does not.

How's the JACM article coming along?  Will you lead with the claim that
the above paragraph is incorrect?

<cut more stuff not about halting or TMs>
-- 
Ben.

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


#172864

FromPete Olcott <Pete@NoEmail.address>
Date2018-02-15 18:43 -0600
Message-ID<PdudnRDuWMC2tBvHnZ2dnUU7-IHNnZ2d@giganews.com>
In reply to#172862
On 2/15/2018 6:15 PM, Ben Bacarisse wrote:
> Pete Olcott <Pete@NoEmail.address> writes:
>
>> On 2/15/2018 3:38 PM, Ben Bacarisse wrote:
>>> Pete Olcott <Pete@NoEmail.address> writes:
> <snip>
>>>> The Liar Paradox is the simplest possible example that I can provide
>>>> that shows a syntactically WFF can indeed be semantically incorrect.
>>> It's not an example of a halting problem.  Unlike this paradox, every
>>> halting problem instance has a correct yes/no answer.  You will never
>>> understand any of your other errors until you accept this basic fact.
>> This error occurs in numerous decision problems:
> There are lots of errors in many decision problems, but here is no error
> in the halting decision problem.
>
> <cut stuff not about halting or TMs>

It it a mandatory prerequisite to any further communication
that you understand and accept that WFF of formal languages
can be semantically incorrect.

For all Formal Language L There exists expressions X of formal
language L such that WFF(X) and Semantically-Incorrect(X).

If you do not understand and accept the above general principle
then it will be impossible to show that

There exists expressions X of Turing Machine Descriptions L
such that WFF(X) and Semantically-Incorrect(X).




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


#172865

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2018-02-16 01:05 +0000
Message-ID<87mv0968wu.fsf@bsb.me.uk>
In reply to#172864
Pete Olcott <Pete@NoEmail.address> writes:

> On 2/15/2018 6:15 PM, Ben Bacarisse wrote:
>> Pete Olcott <Pete@NoEmail.address> writes:
>>
>>> On 2/15/2018 3:38 PM, Ben Bacarisse wrote:
>>>> Pete Olcott <Pete@NoEmail.address> writes:
>> <snip>
>>>>> The Liar Paradox is the simplest possible example that I can provide
>>>>> that shows a syntactically WFF can indeed be semantically incorrect.
>>>> It's not an example of a halting problem.  Unlike this paradox, every
>>>> halting problem instance has a correct yes/no answer.  You will never
>>>> understand any of your other errors until you accept this basic fact.
>>> This error occurs in numerous decision problems:
>> There are lots of errors in many decision problems, but here is no error
>> in the halting decision problem.
>>
>> <cut stuff not about halting or TMs>
>
> It it a mandatory prerequisite to any further communication
> that you understand and accept that WFF of formal languages
> can be semantically incorrect.

I thought we'd reached peek pompous some time ago, but no.

Of course you want to change the subject and that's fine with me -- it
means you will stop talking rubbish about halting.

-- 
Ben.

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


#172868

FromPete Olcott <Pete@NoEmail.address>
Date2018-02-15 19:37 -0600
Message-ID<GIydnfH5BpBKqBvHnZ2dnUU7-WmdnZ2d@giganews.com>
In reply to#172865
On 2/15/2018 7:05 PM, Ben Bacarisse wrote:
> Pete Olcott <Pete@NoEmail.address> writes:
> 
>> On 2/15/2018 6:15 PM, Ben Bacarisse wrote:
>>> Pete Olcott <Pete@NoEmail.address> writes:
>>>
>>>> On 2/15/2018 3:38 PM, Ben Bacarisse wrote:
>>>>> Pete Olcott <Pete@NoEmail.address> writes:
>>> <snip>
>>>>>> The Liar Paradox is the simplest possible example that I can provide
>>>>>> that shows a syntactically WFF can indeed be semantically incorrect.
>>>>> It's not an example of a halting problem.  Unlike this paradox, every
>>>>> halting problem instance has a correct yes/no answer.  You will never
>>>>> understand any of your other errors until you accept this basic fact.
>>>> This error occurs in numerous decision problems:
>>> There are lots of errors in many decision problems, but here is no error
>>> in the halting decision problem.
>>>
>>> <cut stuff not about halting or TMs>
>>
>> It it a mandatory prerequisite to any further communication
>> that you understand and accept that WFF of formal languages
>> can be semantically incorrect.
> 
> I thought we'd reached peek pompous some time ago, but no.
> 
> Of course you want to change the subject and that's fine with me -- it
> means you will stop talking rubbish about halting.
> 

If you cannot think about the halting problem as a David Hilbert
mathematical formalist proof from finite strings to final states
then you won't be able to understand what I am saying.

-- 
*∀L ∈ Formal_Systems
∀X
True(L, X) ↔ ∃Γ ⊆ Axioms(L) Provable(Γ, X) *

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


#172874

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2018-02-16 02:34 +0000
Message-ID<87h8qh64tj.fsf@bsb.me.uk>
In reply to#172868
Pete Olcott <Pete@NoEmail.address> writes:

> On 2/15/2018 7:05 PM, Ben Bacarisse wrote:
<snip>
>> Of course you want to change the subject and that's fine with me -- it
>> means you will stop talking rubbish about halting.
>
> If you cannot think about the halting problem as a David Hilbert
> mathematical formalist proof from finite strings to final states
> then you won't be able to understand what I am saying.

Still denying that every TM computation either halts or does not halt?
Hard to believe it but you are aren't you?

-- 
Ben.

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


#172875

FromPete Olcott <Pete@NoEmail.address>
Date2018-02-15 20:51 -0600
Message-ID<EfednWni8byF2hvHnZ2dnUU7-cfNnZ2d@giganews.com>
In reply to#172874
On 2/15/2018 8:34 PM, Ben Bacarisse wrote:
> Pete Olcott <Pete@NoEmail.address> writes:
> 
>> On 2/15/2018 7:05 PM, Ben Bacarisse wrote:
> <snip>
>>> Of course you want to change the subject and that's fine with me -- it
>>> means you will stop talking rubbish about halting.
>>
>> If you cannot think about the halting problem as a David Hilbert
>> mathematical formalist proof from finite strings to final states
>> then you won't be able to understand what I am saying.
> 
> Still denying that every TM computation either halts or does not halt?
> Hard to believe it but you are aren't you?
> 

I am asserting that every syntactically correct TMD would
either halt or not halt (if executed in a UTM).

Some syntactically correct TMDs can not be proven to halt
or not halt only because they are semantically incorrect.

The formal mathematical proof from their finite string to
their final halting behavior must be aborted before this
proof can be completed because this input string is
semantically incorrect.

Copyright 2018 Pete Olcott

-- 
*∀L ∈ Formal_Systems
∀X
True(L, X) ↔ ∃Γ ⊆ Axioms(L) Provable(Γ, X) *

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


#172876

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2018-02-16 03:32 +0000
Message-ID<87606x624m.fsf@bsb.me.uk>
In reply to#172875
Pete Olcott <Pete@NoEmail.address> writes:

> On 2/15/2018 8:34 PM, Ben Bacarisse wrote:
>> Pete Olcott <Pete@NoEmail.address> writes:
>>
>>> On 2/15/2018 7:05 PM, Ben Bacarisse wrote:
>> <snip>
>>>> Of course you want to change the subject and that's fine with me -- it
>>>> means you will stop talking rubbish about halting.
>>>
>>> If you cannot think about the halting problem as a David Hilbert
>>> mathematical formalist proof from finite strings to final states
>>> then you won't be able to understand what I am saying.
>>
>> Still denying that every TM computation either halts or does not halt?
>> Hard to believe it but you are aren't you?
>
> I am asserting that every syntactically correct TMD would
> either halt or not halt (if executed in a UTM).

Good, that's a start but why are you hedging it by talking about TMDs
rather than TMs, and why are you not talking about computations -- a TM
and some input?  Can you really not bring your self to agree with my
statement?

Every TM computation -- that's a TM and an input string on an otherwise
blank tape -- either halts or does not halt.  Can't you agree to that?

> Some syntactically correct TMDs can not be proven to halt
> or not halt only because they are semantically incorrect.

That may be, but it's irrelevant.  The question is whether they halt or
not, not what can be proven about them.

-- 
Ben.

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


#172877

FromPete Olcott <Pete@NoEmail.address>
Date2018-02-15 22:42 -0600
Message-ID<xsKdnfETaOzJ_BvHnZ2dnUU7-TnNnZ2d@giganews.com>
In reply to#172876
On 2/15/2018 9:32 PM, Ben Bacarisse wrote:
> Pete Olcott <Pete@NoEmail.address> writes:
> 
>> On 2/15/2018 8:34 PM, Ben Bacarisse wrote:
>>> Pete Olcott <Pete@NoEmail.address> writes:
>>>
>>>> On 2/15/2018 7:05 PM, Ben Bacarisse wrote:
>>> <snip>
>>>>> Of course you want to change the subject and that's fine with me -- it
>>>>> means you will stop talking rubbish about halting.
>>>>
>>>> If you cannot think about the halting problem as a David Hilbert
>>>> mathematical formalist proof from finite strings to final states
>>>> then you won't be able to understand what I am saying.
>>>
>>> Still denying that every TM computation either halts or does not halt?
>>> Hard to believe it but you are aren't you?
>>
>> I am asserting that every syntactically correct TMD would
>> either halt or not halt (if executed in a UTM).
> 
> Good, that's a start but why are you hedging it by talking about TMDs
> rather than TMs, and why are you not talking about computations -- a TM
> and some input?  Can you really not bring your self to agree with my
> statement?
> 

The ONLY correct way to analyze this problem is as a David Hilbert
mathematical formalist proof from finite strings to final states.

I can never hedge on this mandatory requirement to the slightest trace
of an infinitesimal degree.

> Every TM computation -- that's a TM and an input string on an otherwise
> blank tape -- either halts or does not halt.  Can't you agree to that?
> 

Already did.

>> Some syntactically correct TMDs can not be proven to halt
>> or not halt only because they are semantically incorrect.
> 
> That may be, but it's irrelevant.  The question is whether they halt or
> not, not what can be proven about them.
> 

 From a mathematical proof POV the input is semantically incorrect.

The ONLY reason that this proof cannot be completed is that the
input is inherently infinitely recursive so the evaluation of this
input must be terminated before the input TMD can be traced to
its halting or non halting behavior.

So H transitions to its H.qpsr state indicating that [Ĥx] [Ĥx] has the
semantically erroneous property of pathological self-reference(Olcott 2004).

I think that one just refuted Rice. I remember that we argued about this
years ago and you said it was impossible because of Rice.

The concrete instance of the adapted Linz example shows that PSR can
be detected and reported. I could write a halt decider myself for
the class of machines specified by [Ĥx] or [Ĥ] or [H'].

Copyright 2018 Pete Olcott (and many other years since 2004)
                    see comp.theory and sci.logic for details.

-- 
*∀L ∈ Formal_Systems
∀X
True(L, X) ↔ ∃Γ ⊆ Axioms(L) Provable(Γ, X) *

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


#172886

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2018-02-16 12:06 +0000
Message-ID<87a7w93zqn.fsf@bsb.me.uk>
In reply to#172877
Pete Olcott <Pete@NoEmail.address> writes:

> On 2/15/2018 9:32 PM, Ben Bacarisse wrote:
>> Pete Olcott <Pete@NoEmail.address> writes:
>>
>>> On 2/15/2018 8:34 PM, Ben Bacarisse wrote:
>>>> Pete Olcott <Pete@NoEmail.address> writes:
>>>>
>>>>> On 2/15/2018 7:05 PM, Ben Bacarisse wrote:
>>>> <snip>
>>>>>> Of course you want to change the subject and that's fine with me -- it
>>>>>> means you will stop talking rubbish about halting.
>>>>>
>>>>> If you cannot think about the halting problem as a David Hilbert
>>>>> mathematical formalist proof from finite strings to final states
>>>>> then you won't be able to understand what I am saying.
>>>>
>>>> Still denying that every TM computation either halts or does not halt?
>>>> Hard to believe it but you are aren't you?
>>>
>>> I am asserting that every syntactically correct TMD would
>>> either halt or not halt (if executed in a UTM).
>>
>> Good, that's a start but why are you hedging it by talking about TMDs
>> rather than TMs, and why are you not talking about computations -- a TM
>> and some input?  Can you really not bring your self to agree with my
>> statement?
>
> The ONLY correct way to analyze this problem is as a David Hilbert
> mathematical formalist proof from finite strings to final states.

Now this is a nother problem.  You say below that you do agree with my
wording and the you don't hedge, so what is this apparent disagreement
about?

> I can never hedge on this mandatory requirement to the slightest trace
> of an infinitesimal degree.

>> Every TM computation -- that's a TM and an input string on an otherwise
>> blank tape -- either halts or does not halt.  Can't you agree to that?
>
> Already did.

OK, I must have missed it.  (Above you talked about TMDs not TMs and you
made no reference to computations.)

Anyway, no matter, you do it seems agree with what I said.

The next thing is whether you agree that every finite string either
encodes a syntactically correct TM/input pair or it does not.  Do you
deny this rather obvious fact?

> I could write a halt decider myself for
> the class of machines specified by [Ĥx] or [Ĥ] or [H'].

Anyone can.  It's an empty set.  There is no more trivial decision
problem.

-- 
Ben.

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


#172908

FromPete Olcott <Pete@NoEmail.address>
Date2018-02-16 10:26 -0600
Message-ID<rf-dnQ4gZOupmxrHnZ2dnUU7-IXNnZ2d@giganews.com>
In reply to#172886
On 2/16/2018 6:06 AM, Ben Bacarisse wrote:
> Pete Olcott <Pete@NoEmail.address> writes:
> 
>> On 2/15/2018 9:32 PM, Ben Bacarisse wrote:
>>> Pete Olcott <Pete@NoEmail.address> writes:
>>>
>>>> On 2/15/2018 8:34 PM, Ben Bacarisse wrote:
>>>>> Pete Olcott <Pete@NoEmail.address> writes:
>>>>>
>>>>>> On 2/15/2018 7:05 PM, Ben Bacarisse wrote:
>>>>> <snip>
>>>>>>> Of course you want to change the subject and that's fine with me -- it
>>>>>>> means you will stop talking rubbish about halting.
>>>>>>
>>>>>> If you cannot think about the halting problem as a David Hilbert
>>>>>> mathematical formalist proof from finite strings to final states
>>>>>> then you won't be able to understand what I am saying.
>>>>>
>>>>> Still denying that every TM computation either halts or does not halt?
>>>>> Hard to believe it but you are aren't you?
>>>>
>>>> I am asserting that every syntactically correct TMD would
>>>> either halt or not halt (if executed in a UTM).
>>>
>>> Good, that's a start but why are you hedging it by talking about TMDs
>>> rather than TMs, and why are you not talking about computations -- a TM
>>> and some input?  Can you really not bring your self to agree with my
>>> statement?
>>
>> The ONLY correct way to analyze this problem is as a David Hilbert
>> mathematical formalist proof from finite strings to final states.
> 
> Now this is a nother problem.  You say below that you do agree with my
> wording and the you don't hedge, so what is this apparent disagreement
> about?

You need the right tool for the job. David Hilbert formalist mathematical
proof from finite strings to final halt states in the formal language of
Turing Machine Descriptions is the right tool for the job.

Without this tool the analysis becomes equivocal, with this tool the analysis
is unequivocal.

> 
>> I can never hedge on this mandatory requirement to the slightest trace
>> of an infinitesimal degree.
> 
>>> Every TM computation -- that's a TM and an input string on an otherwise
>>> blank tape -- either halts or does not halt.  Can't you agree to that?
>>
>> Already did.
> 
> OK, I must have missed it.  (Above you talked about TMDs not TMs and you
> made no reference to computations.)
> 

Of course I did not make any reference to computations a finite string
just sits there unless it is executed by a UTM.

> Anyway, no matter, you do it seems agree with what I said.
> 

Although you said it on USENET first, I figured out that [Ĥx] must
halt on its input if H is a halt decider two days before you said it.

> The next thing is whether you agree that every finite string either
> encodes a syntactically correct TM/input pair or it does not.  Do you
> deny this rather obvious fact?

I agree yet doesn't Rice say that this is undecidable? Maybe not:
In computability theory, Rice's theorem states that all non-trivial,
semantic properties of programs are undecidable.

> 
>> I could write a halt decider myself for
>> the class of machines specified by [Ĥx] or [Ĥ] or [H'].
> 
> Anyone can.  It's an empty set.  There is no more trivial decision
> problem.
> 

This is a place in your analysis where you seem to get wacky. Last night
you even said the finite strings do not exist:

On 2/15/2018 6:15 PM, Ben Bacarisse wrote:
No string of the form [H^x][H^x] exists.

<wacky>
These words right here do not exist and you did not just read them!
</wacky>

I could write a halt decider for the above finite string that decides
(1) Is a correct TMD that would halt on its input.
(2) Is a correct TMD that would not halt on its input.
(3) Is not a correct TMD.

a) H [H] [H2]    H.qy
b) H [H'][H'2]   H.qn   [H'2] halts on null input causing [H'].qy causing H.qn
c) H [Ĥx][Ĥx2]   H.qpsr    pathological self-reference(Olcott 2004)
d) H [Ĥ] [Ĥ2]    H.qpsr    pathological self-reference(Olcott 2004)

a)  Correct &  Halts
b)  Correct & ~Halts
c) ~Correct
d) ~Correct

http://liarparadox.org/index.php/2018/01/18/refutation-of-the-halting-problem-proof/
This now contains a state transition sequence and state transition diagram for
{H, Ĥ, and Ĥx} as Figures 12.1, 12.3, and 12.4

Since the David Hilbert formalist proof from finite strings to final states
is identical for H [Ĥx][Ĥx] and H [Ĥ][Ĥ], the latter one is not shown.

-- 
*∀L ∈ Formal_Systems
∀X
True(L, X) ↔ ∃Γ ⊆ Axioms(L) Provable(Γ, X) *

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


#172948

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2018-02-16 20:42 +0000
Message-ID<87zi481xao.fsf@bsb.me.uk>
In reply to#172908
Pete Olcott <Pete@NoEmail.address> writes:

> On 2/16/2018 6:06 AM, Ben Bacarisse wrote:
>> Pete Olcott <Pete@NoEmail.address> writes:
>>
>>> On 2/15/2018 9:32 PM, Ben Bacarisse wrote:
<snip>
>>>> Every TM computation -- that's a TM and an input string on an otherwise
>>>> blank tape -- either halts or does not halt.  Can't you agree to that?
>>>
>>> Already did.
>>
>> OK, I must have missed it.  (Above you talked about TMDs not TMs and you
>> made no reference to computations.)
>
> Of course I did not make any reference to computations a finite string
> just sits there unless it is executed by a UTM.

So don't say you "already did" agree if you don't.  I am trying to find
out if you still disagree (as you once did) with this basic fact:

  Every TM computation -- that's a TM acting on an input string on an
  otherwise blank tape -- either halts or does not halt.

It's a statement about TMs, not encodings of TMs, and it's about
computations (a TM and an input) not just about TMs.  I think you still
deny it but I'd rather you say so explicitly.

<snip>
> This is a place in your analysis where you seem to get wacky. Last night
> you even said the finite strings do not exist:
>
> On 2/15/2018 6:15 PM, Ben Bacarisse wrote:
> No string of the form [H^x][H^x] exists.
>
> <wacky>
> These words right here do not exist and you did not just read them!
> </wacky>

Do you really not know what I mean?  If you don't know what I mean, it's
like this:

Let [X] denote the string of binary digits that encode the natural
number X.  Let H be an even prime other than two, and from it construct
H^x by adding 42 to H.  There are no strings of the form [H^x].  There
is a string of the form "[H^x]" -- in fact I've just typed it twice --
but there are no strings of the form [H^x], i.e. binary digits of 42
more than some even prime other than two.

To switch back to your case, [H^x] denotes the binary encoding of
something that does not exist.

-- 
Ben.

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


#172955

Frompeteolcott <peterolcott2@gmail.com>
Date2018-02-16 13:16 -0800
Message-ID<792611e2-ca3c-4b80-8d00-e815ede4419c@googlegroups.com>
In reply to#172948
On Friday, February 16, 2018 at 2:42:36 PM UTC-6, Ben Bacarisse wrote:
> Pete Olcott <Pete@NoEmail.address> writes:
> 
> > On 2/16/2018 6:06 AM, Ben Bacarisse wrote:
> >> Pete Olcott <Pete@NoEmail.address> writes:
> >>
> >>> On 2/15/2018 9:32 PM, Ben Bacarisse wrote:
> <snip>
> >>>> Every TM computation -- that's a TM and an input string on an otherwise
> >>>> blank tape -- either halts or does not halt.  Can't you agree to that?
> >>>
> >>> Already did.
> >>
> >> OK, I must have missed it.  (Above you talked about TMDs not TMs and you
> >> made no reference to computations.)
> >
> > Of course I did not make any reference to computations a finite string
> > just sits there unless it is executed by a UTM.
> 
> So don't say you "already did" agree if you don't.  I am trying to find
> out if you still disagree (as you once did) with this basic fact:
> 
>   Every TM computation -- that's a TM acting on an input string on an
>   otherwise blank tape -- either halts or does not halt.
> 

If we assume that chracters of the finite string TMD has 
been verified as a syntactically correct WFF in the language 
of Turing Machine descriptions then yes. 

I am not sure about the case where the first half is a TMD and 
the last half is an English poem. 

> It's a statement about TMs, not encodings of TMs, and it's about
> computations (a TM and an input) not just about TMs.  I think you still
> deny it but I'd rather you say so explicitly.
> 

I am only going to talk about TMDs because I am only going to talk
about David Hilbert formal proofs from finite strings to final states. 

> <snip>
> > This is a place in your analysis where you seem to get wacky. Last night
> > you even said the finite strings do not exist:
> >
> > On 2/15/2018 6:15 PM, Ben Bacarisse wrote:
> > No string of the form [H^x][H^x] exists.
> >
> > <wacky>
> > These words right here do not exist and you did not just read them!
> > </wacky>
> 
> Do you really not know what I mean?  If you don't know what I mean, it's
> like this:
> 

You have to say exactly and precisely what you mean and mean exactly 
and precisely what you say or your words be be determined to be wacky. 
Those quoted words were wacky. 

> Let [X] denote the string of binary digits that encode the natural
> number X.  Let H be an even prime other than two, and from it construct
> H^x by adding 42 to H.  There are no strings of the form [H^x].  There
> is a string of the form "[H^x]" -- in fact I've just typed it twice --
> but there are no strings of the form [H^x], i.e. binary digits of 42
> more than some even prime other than two.
> 

Self-contradictory specifications define the empty set. 

> To switch back to your case, [H^x] denotes the binary encoding of
> something that does not exist.
> 
> -- 
> Ben.

You are simply assuming that based on your belief that it has been
correctly proven. 

H transitions to H.qy if its input string is a correct TMD that 
halts on its input else H transitions to H.qn

It is unequivocally proven that semantic errors count as errors:
https://en.wikipedia.org/wiki/Colorless_green_ideas_sleep_furiously 

As soon as the semantic error is formalized syntactically then a
key gap in the inference chain is closed such that WFF(L, [Ĥx]) → FALSE
where L is the language of Turing Machine Descriptions. 

The key problems with closing this gap were:
(1) No one knew the gap existed.
(2) Everyone assumed that Rice's Theorem would make closing the gap impossible. 
(3) Pathological self-reference(Olcott 2004) has never before been sufficiently formalized.

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


#172965

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2018-02-16 23:01 +0000
Message-ID<87o9ko1qva.fsf@bsb.me.uk>
In reply to#172955
peteolcott <peterolcott2@gmail.com> writes:

> On Friday, February 16, 2018 at 2:42:36 PM UTC-6, Ben Bacarisse wrote:
>> Pete Olcott <Pete@NoEmail.address> writes:
>> 
>> > On 2/16/2018 6:06 AM, Ben Bacarisse wrote:
>> >> Pete Olcott <Pete@NoEmail.address> writes:
>> >>
>> >>> On 2/15/2018 9:32 PM, Ben Bacarisse wrote:
>> <snip>
>> >>>> Every TM computation -- that's a TM and an input string on an otherwise
>> >>>> blank tape -- either halts or does not halt.  Can't you agree to that?
>> >>>
>> >>> Already did.
>> >>
>> >> OK, I must have missed it.  (Above you talked about TMDs not TMs and you
>> >> made no reference to computations.)
>> >
>> > Of course I did not make any reference to computations a finite string
>> > just sits there unless it is executed by a UTM.
>> 
>> So don't say you "already did" agree if you don't.  I am trying to find
>> out if you still disagree (as you once did) with this basic fact:
>> 
>>   Every TM computation -- that's a TM acting on an input string on an
>>   otherwise blank tape -- either halts or does not halt.
>
> If we assume that chracters of the finite string TMD has 
> been verified as a syntactically correct WFF in the language 
> of Turing Machine descriptions then yes.

You refuse to agree and instead talk about "the finite string TMD" which
has nothing to do with what I said.

I am finding it hard to consider this an honest exchange.  You could say
"no, I don't accept that every TM computation either halts or does not
halt", or you could just say "yes, I agree".  Instead you equivocate.

Oh well, not answering is the same as denying this fact.  If you
continue to pretend to talk about halting I shall remind people that you
do not accept that every TM computation either halts or does not halt.

>> > On 2/15/2018 6:15 PM, Ben Bacarisse wrote:
>> > No string of the form [H^x][H^x] exists.
<snip>
> Self-contradictory specifications define the empty set.

Yes, there are no strings that encode machines with the behaviour you
require of H^x.  Therefore there are no strings that encode such
machines, which is what [H^x] denotes.

> You are simply assuming that based on your belief that it has been
> correctly proven.

No, I am basing that on having understood the proof of the theorem.
You, on the other hand, don't even understand the halting problem.  You
won't accept the plain fact that every TM computation either halts or
does not halt.  From that point on, there is not reason to take anything
you say seriously.  I am fool to read on but I did...

> H transitions to H.qy if its input string is a correct TMD that 
> halts on its input else H transitions to H.qn

That's the PO-halting problem that no one but you cares about.  Your H
rejects some encoded computations on the basis of them being "incorrect"
rather than on the halting or otherwise of the computation.

> It is unequivocally proven that semantic errors count as errors:
> https://en.wikipedia.org/wiki/Colorless_green_ideas_sleep_furiously

Will that be the citation for your claim that some halting instances
don't have a correct yes/no answer when you write your paper for the
Journal of the ACM?

That wiki article is not about halting instances, of course.  They are
much simpler and have the property that every halting instance has a
correct yes/no answer.  But you deny this reality and prefer to live in
a world where some TM computations don't either halt or not halt.

> As soon as the semantic error is formalized syntactically then a
> key gap in the inference chain is closed such that WFF(L, [Ĥx]) → FALSE
> where L is the language of Turing Machine Descriptions. 
>
> The key problems with closing this gap were:
> (1) No one knew the gap existed.
> (2) Everyone assumed that Rice's Theorem would make closing the gap impossible. 
> (3) Pathological self-reference(Olcott 2004) has never before been
> sufficiently formalized.

No one cares about a decider that rejects some cases for any reason
other than not halting.

-- 
Ben.

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


#172970

FromPete Olcott <Pete@NoEmail.address>
Date2018-02-16 17:48 -0600
Message-ID<tuKdnU7te_VQ8BrHnZ2dnUU7-LnNnZ2d@giganews.com>
In reply to#172965
On 2/16/2018 5:01 PM, Ben Bacarisse wrote:
> peteolcott <peterolcott2@gmail.com> writes:
> 
>> On Friday, February 16, 2018 at 2:42:36 PM UTC-6, Ben Bacarisse wrote:
>>> Pete Olcott <Pete@NoEmail.address> writes:
>>>
>>>> On 2/16/2018 6:06 AM, Ben Bacarisse wrote:
>>>>> Pete Olcott <Pete@NoEmail.address> writes:
>>>>>
>>>>>> On 2/15/2018 9:32 PM, Ben Bacarisse wrote:
>>> <snip>
>>>>>>> Every TM computation -- that's a TM and an input string on an otherwise
>>>>>>> blank tape -- either halts or does not halt.  Can't you agree to that?
>>>>>>
>>>>>> Already did.
>>>>>
>>>>> OK, I must have missed it.  (Above you talked about TMDs not TMs and you
>>>>> made no reference to computations.)
>>>>
>>>> Of course I did not make any reference to computations a finite string
>>>> just sits there unless it is executed by a UTM.
>>>
>>> So don't say you "already did" agree if you don't.  I am trying to find
>>> out if you still disagree (as you once did) with this basic fact:
>>>
>>>    Every TM computation -- that's a TM acting on an input string on an
>>>    otherwise blank tape -- either halts or does not halt.
>>
>> If we assume that chracters of the finite string TMD has
>> been verified as a syntactically correct WFF in the language
>> of Turing Machine descriptions then yes.
> 
> You refuse to agree and instead talk about "the finite string TMD" which
> has nothing to do with what I said.
> 
> I am finding it hard to consider this an honest exchange.  You could say
> "no, I don't accept that every TM computation either halts or does not
> halt", or you could just say "yes, I agree".  Instead you equivocate.
> 

I simply have not had time to carefully ponder the case where the
first half of a TMD is a valid TMD and the second half is an English
poem. What would a UTM do with a case like this?

Every syntactically correct TMD would either halt or fail to halt when
executed within a UTM.

If we assume that there is some sort of syntax checker that accepts or
rejects TMD as syntactically correct then all of these would either
halt or fail to halt.

> Oh well, not answering is the same as denying this fact.  If you
> continue to pretend to talk about halting I shall remind people that you
> do not accept that every TM computation either halts or does not halt.
> 

Every TM computation halts or fails to halt.

>>>> On 2/15/2018 6:15 PM, Ben Bacarisse wrote:
>>>> No string of the form [H^x][H^x] exists.
> <snip>
>> Self-contradictory specifications define the empty set.
> 
> Yes, there are no strings that encode machines with the behaviour you
> require of H^x.  Therefore there are no strings that encode such
> machines, which is what [H^x] denotes.
> 

That is not true and no one in the world can prove it.

>> You are simply assuming that based on your belief that it has been
>> correctly proven.
> 
> No, I am basing that on having understood the proof of the theorem.

Yet you are not augmenting this understanding with my qualifications.
You are simply assuming away all of my objections.

> You, on the other hand, don't even understand the halting problem.  You
> won't accept the plain fact that every TM computation either halts or
> does not halt.  

Every TM computation halts or does not halt. It is hard telling
what incorrect TMD's would do.

> From that point on, there is not reason to take anything
> you say seriously.  I am fool to read on but I did...
> 
>> H transitions to H.qy if its input string is a correct TMD that
>> halts on its input else H transitions to H.qn
> 
> That's the PO-halting problem that no one but you cares about.  

First of all we agreed years ago that English poems get a H.qn,
so the above is the same halting problem as always.

That no one cares about the semantic gaps in the formal proofs is why
they have remained wrong for all of these years.

> Your H
> rejects some encoded computations on the basis of them being "incorrect"
> rather than on the halting or otherwise of the computation.
> 

Yes the next level of error detection beyond syntax.

>> It is unequivocally proven that semantic errors count as errors:
>> https://en.wikipedia.org/wiki/Colorless_green_ideas_sleep_furiously
> 
> Will that be the citation for your claim that some halting instances
> don't have a correct yes/no answer when you write your paper for the
> Journal of the ACM?

It is proof that one cannot ignore semantics and remain coherent. Millions
of formal proofs are all incorrect because they think that semantics does
not count only because it has not yet been formalized syntactically.

So I will formalize it syntactically.

> 
> That wiki article is not about halting instances, of course.  They are
> much simpler and have the property that every halting instance has a
> correct yes/no answer.  But you deny this reality and prefer to live in
> a world where some TM computations don't either halt or not halt.
> 

The Wiki article proves that semantics cannot be ignored.

>> As soon as the semantic error is formalized syntactically then a
>> key gap in the inference chain is closed such that WFF(L, [Ĥx]) → FALSE
>> where L is the language of Turing Machine Descriptions.
>>
>> The key problems with closing this gap were:
>> (1) No one knew the gap existed.
>> (2) Everyone assumed that Rice's Theorem would make closing the gap impossible.
>> (3) Pathological self-reference(Olcott 2004) has never before been
>> sufficiently formalized.
> 
> No one cares about a decider that rejects some cases for any reason
> other than not halting.
> 

That is why millions of math proofs remain incorrect. Semantics
cannot be ignored.

-- 
*∀L ∈ Formal_Systems
∀X
True(L, X) ↔ ∃Γ ⊆ Axioms(L) Provable(Γ, X) *

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


#172985

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2018-02-17 01:33 +0000
Message-ID<87606w1jt1.fsf@bsb.me.uk>
In reply to#172970
Pete Olcott <Pete@NoEmail.address> writes:

> On 2/16/2018 5:01 PM, Ben Bacarisse wrote:
<snip>
>> Oh well, not answering is the same as denying this fact.  If you
>> continue to pretend to talk about halting I shall remind people that you
>> do not accept that every TM computation either halts or does not halt.
>
> Every TM computation halts or fails to halt.

Great.

Do you also accept that every finite string either encodes a TM
computation or it does not?

The encoding has to be agreed, of course, but something simple like the
binary bits of the ASCII characters used to write out the transitions,
the input string, and the number of the final (AKA accepting) state.
Here's a computation:

  0,1R1>1;1,0R0>0/1/101

though the actual string is the zeros and ones of those ASCII bytes

There are two states (0 and 1) and two transitions.  From state 0 a tape
symbol of 1 cases a move right, a write of 1 to the tape, and the TM
enters state 1.  From state 1 seeing a 0 cases the head to move right, a
0 to be written and the machine goes to state 0.  The final state is
state 1, and the input for this computation is 101.  This computation
halts (and, as it happens, it "accepts" since it halts in state 1).

This:

  Then hate me when thou wilt; if ever, now;

is not a TM computation and neither are

  0,1R1>1;1,0R0>01/101

nor

  0,1R1>1;11,0R0>0/1/101

Other non-computations include 0/1 sequences that are not a multiple of
8 long or any that include anything but the ASCII characters

  0 1 2 3 4 5 6 7 8 9 L R > , / ;

So, we have a simple encoding and a simple question: does every finite
string of bits either encode a TM computation or not?

>>>>> On 2/15/2018 6:15 PM, Ben Bacarisse wrote:
>>>>> No string of the form [H^x][H^x] exists.
>> <snip>
>>> Self-contradictory specifications define the empty set.
>>
>> Yes, there are no strings that encode machines with the behaviour you
>> require of H^x.  Therefore there are no strings that encode such
>> machines, which is what [H^x] denotes.
>
> That is not true and no one in the world can prove it.

It's been proven.  Lots of times.  In lots of ways.

>>> You are simply assuming that based on your belief that it has been
>>> correctly proven.
>>
>> No, I am basing that on having understood the proof of the theorem.
>
> Yet you are not augmenting this understanding with my qualifications.
> You are simply assuming away all of my objections.

Your current qualification is to claim that the "halting problem" is
something other than the subject of the theorem.  Until you drop that
change and accept what the theorem is about (halting and not
PO-halting), nothing you say has any bearing on it.

<snip>
>> No one cares about a decider that rejects some cases for any reason
>> other than not halting.
>
> That is why millions of math proofs remain incorrect. Semantics
> cannot be ignored.

That a nice clear statement that you are not talking about the halting
theorem.  In your view the theorem is about the wrong thing -- purely
syntactic halting.  Why you can't just accept it I don't know since it's
not a theorem about the problem you (and you alone) care about.

-- 
Ben.

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


#172987

Fromgrahamcooper7@gmail.com
Date2018-02-16 17:49 -0800
Message-ID<c6f5eb83-b7a5-480e-b25d-f2efbb7478da@googlegroups.com>
In reply to#172985
On Saturday, February 17, 2018 at 11:33:52 AM UTC+10, Ben Bacarisse wrote:
> Pete Olcott <Pete@NoEmail.address> writes:
> 
> > On 2/16/2018 5:01 PM, Ben Bacarisse wrote:
> <snip>
> >> Oh well, not answering is the same as denying this fact.  If you
> >> continue to pretend to talk about halting I shall remind people that you
> >> do not accept that every TM computation either halts or does not halt.
> >
> > Every TM computation halts or fails to halt.
> 
> Great.
> 
> Do you also accept that every finite string either encodes a TM
> computation or it does not?
> 
> The encoding has to be agreed, of course, but something simple like the
> binary bits of the ASCII characters used to write out the transitions,
> the input string, and the number of the final (AKA accepting) state.
> Here's a computation:
> 
>   0,1R1>1;1,0R0>0/1/101
> 
> though the actual string is the zeros and ones of those ASCII bytes
> 
> There are two states (0 and 1) and two transitions.  From state 0 a tape
> symbol of 1 cases a move right, a write of 1 to the tape, and the TM
> enters state 1.  From state 1 seeing a 0 cases the head to move right, a
> 0 to be written and the machine goes to state 0.  The final state is
> state 1, and the input for this computation is 101.  This computation
> halts (and, as it happens, it "accepts" since it halts in state 1).
> 
> This:
> 
>   Then hate me when thou wilt; if ever, now;
> 
> is not a TM computation and neither are
> 
>   0,1R1>1;1,0R0>01/101
> 
> nor
> 
>   0,1R1>1;11,0R0>0/1/101
> 
> Other non-computations include 0/1 sequences that are not a multiple of
> 8 long or any that include anything but the ASCII characters
> 
>   0 1 2 3 4 5 6 7 8 9 L R > , / ;
> 
> So, we have a simple encoding and a simple question: does every finite
> string of bits either encode a TM computation or not?


CONTEXT APPLIES


Its trivial to enumerate Turing Machines



TM1
1 0 0 0 1
1 1 0 0 1

TM2
1 0 0 0 2
1 1 0 0 2

TM3
1 0 0 0 2
1 0 0 1 2



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


#173283

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2018-02-19 15:48 +0000
Message-ID<87fu5x3rra.fsf@bsb.me.uk>
In reply to#172985
Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Pete Olcott <Pete@NoEmail.address> writes:
>
>> On 2/16/2018 5:01 PM, Ben Bacarisse wrote:
> <snip>
>>> Oh well, not answering is the same as denying this fact.  If you
>>> continue to pretend to talk about halting I shall remind people that you
>>> do not accept that every TM computation either halts or does not halt.
>>
>> Every TM computation halts or fails to halt.
>
> Great.
>
> Do you also accept that every finite string either encodes a TM
> computation or it does not?

I was going to leave this but I see you have decided to keep posting
incorrect things about halting elsewhere.  So I have to ask why have you
not answered this question?

I suspect you feel a bit cornered.  You can't possibly deny that obvious
answer but you need to deny it or it will be clear that your notion of
rejecting some strings based on something other than the halting nature
of the encoded computation is not the halting problem at all, but your
own pointless version of it.

> The encoding has to be agreed, of course, but something simple like the
> binary bits of the ASCII characters used to write out the transitions,
> the input string, and the number of the final (AKA accepting) state.
> Here's a computation:
>
>   0,1R1>1;1,0R0>0/1/101
>
> though the actual string is the zeros and ones of those ASCII bytes
>
> There are two states (0 and 1) and two transitions.  From state 0 a tape
> symbol of 1 cases a move right, a write of 1 to the tape, and the TM
> enters state 1.  From state 1 seeing a 0 cases the head to move right, a
> 0 to be written and the machine goes to state 0.  The final state is
> state 1, and the input for this computation is 101.  This computation
> halts (and, as it happens, it "accepts" since it halts in state 1).
>
> This:
>
>   Then hate me when thou wilt; if ever, now;
>
> is not a TM computation and neither are
>
>   0,1R1>1;1,0R0>01/101
>
> nor
>
>   0,1R1>1;11,0R0>0/1/101
>
> Other non-computations include 0/1 sequences that are not a multiple of
> 8 long or any that include anything but the ASCII characters
>
>   0 1 2 3 4 5 6 7 8 9 L R > , / ;
>
> So, we have a simple encoding and a simple question: does every finite
> string of bits either encode a TM computation or not?

With en explicit encoding it's very clear what the answer has to be, but
I think you can't see a way out if you were to agree.

> <snip>
>>> No one cares about a decider that rejects some cases for any reason
>>> other than not halting.
>>
>> That is why millions of math proofs remain incorrect. Semantics
>> cannot be ignored.
>
> That a nice clear statement that you are not talking about the halting
> theorem.  In your view the theorem is about the wrong thing -- purely
> syntactic halting.  Why you can't just accept it I don't know since it's
> not a theorem about the problem you (and you alone) care about.

-- 
Ben.

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


#173539

FromPete Olcott <Pete@NoEmail.address>
Date2018-02-22 15:31 -0600
Message-ID<wbadnSDMZaZcqxLHnZ2dnUU7-VnNnZ2d@giganews.com>
In reply to#172985
On 2/22/2018 2:40 PM, David Kleinecke wrote:
> On Thursday, February 22, 2018 at 11:25:25 AM UTC-8, Pete Olcott wrote:
>>
>>      I am not going
>>          to accept any hodge podge, spur of the moment, seat of the pants
>>          specification for the language of Turing Machine Descriptions
>>          when a perfect tried and true specification is right here:
>>
>>        
>>
>>            http://www.lns.mit.edu/~dsw/turing/turing.html
> 
> I think that program is a bit over-engineered but the real
> problem with it is that I couldn't find the description of
> the quintuple state code. 

 From paren.tm

This is a well-formed parentheses string checker.
Adopted from Prather, page 481.  (Note that the left parenthesis
has three contexts in this file.)

This was the case where I had to buy a used text book
just to find out the missing details of his specification.

https://www.amazon.com/Discrete-Mathematical-Structures-Computer-Science/dp/0395206227
Yes I found that I did buy this book for this reason.

So apparently the author of the Turing Machine interpreter did
not document the language of his interpreter out of some lack of
understanding of copyright fair use.

I am not going to take the time to carefully analyze this because
the whole issue is moot. We simply assume that a deterministic
finite automaton exists that can decide whether or not a finite
string is a syntactically correct Turing Machine Description or not.

For a machine language as simple as the TMD language this would be trivial.
It would be 100,000-fold simpler than the DFA of my patents:
US Patents 7,046,848 9,171,207

> That code is the guts of a Turing
> Machine and I would would like to see why a quintuple is
> involved because, so far as I can see, a Turing Machine state
> has six attributes (plus some states being stop states).
> 
>  From my POV a Turing Machine state is a pair of actions -
> one that applies when the cell under the read is marked
> and one that applies when it isn't. Each action has three
> attributes - two booleans for mark or not-mark the cell,
> and increment or decrement the cell and an identifier for
> the next state. I may be mistaken in my idea of a Turing
> Machine but I can't discover yours in your reference.
>   
> 

I am not sure whether or not the reference is complete or not.
I did buy the referenced textbook just in case.

-- 
*∀L ∈ Formal_Systems
∀X
True(L, X) ↔ ∃Γ ⊆ Axioms(L) Provable(Γ, X) *

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


#172884

Fromgrahamcooper7@gmail.com
Date2018-02-16 02:53 -0800
Message-ID<c32758ed-fd99-426a-82fb-a8dc73c2b415@googlegroups.com>
In reply to#172876
On Friday, February 16, 2018 at 1:32:16 PM UTC+10, Ben Bacarisse wrote:
> Pete Olcott <Pete@NoEmail.address> writes:
> 
> 
> > Some syntactically correct TMDs can not be proven to halt
> > or not halt only because they are semantically incorrect.
> 
> That may be, but it's irrelevant.  The question is whether they halt or
> not, not what can be proven about them.


Seems relevant to the Halting Problem!

Pete seems more concerned with the realisation of testing halt values
than an infinite subset of points in [TM,INPUT] NXN being un-computable.

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


#172776

FromAndy Walker <anw@cuboid.co.uk>
Date2018-02-15 12:24 +0000
Message-ID<p63u5p$b5d$1@gioia.aioe.org>
In reply to#172749
On 14/02/18 23:22, Pete Olcott wrote:
>>> [... W]e know that a halt decider is defined
>>> to do a debug trace on its input until:
>>> (1) Halting behavior is detected.
>>> (2) Non-Halting behavior is detected.
>>> (3) Erroneous input is detected.
>>      Wait!  In what world is that the *definition* of a halt decider?
>> Indeed, it is almost [but not quite] trivial that by such a definition
>> there can be no such thing.  Specifically, how do you expect a HD to
>> detect non-halting behaviour? 
> You never heard a a loop that lacks a loop termination condition?

	Of course.  But the question was not that, but how you expect a
HD to detect non-halting behaviour.  See below.

> If not you haven't the slightest basis to even begin critiquing my work.

	Why not shoot the messenger?

[...]
> Every conventional HP proof specifies an infinitely recursive
> evaluation sequence because every conventional proof operates
> on a pair of TMD's and each TMD always requires its own pair
> of inputs. I was surprised that it took me more than a dozen
> years and 3000 hours to notice this.

	So is everyone else here, as it is obvious nonsense.  A
TMD is just that;  a description.  It does not require any input,
any more than any computer program *source* requires an input.
If there was any merit whatsoever in your claim, then UTMs would
be impossible for the same reason.

>>      Emulating/tracing a TM-input pair can show that the TM halts
>> with that input;  it cannot show directly that it does not halt*.  For
> As soon as it detects a loop that lacks a loop termination condition
> it breaks out of the debug trace and transitions to its H.qn decision state.

	The relevant questions are not whether there is a loop with no
termination condition, but whether any such loop [inc indirect loops
such as recursion] actually terminates, and how this can be detected.

>> that you need more sophisticated arguments [of which there are many].
>> The essence of the HP discussion is to show that no such argument [or
>> collection of them] is sufficient in general.
> No my case is relatively simple every single counter-example to the
> claim that a halt decider does not exist is semantically incorrect
> thus not a counter-example at all.

	As the standard proof shows that no counter-example to that
claim can exist, your case is confused.

[...]
> The debug trace is not a mindless emulation. At every step of the trace
> it is looking for a loop that lacks a loop termination condition. As
> soon as it finds one it breaks out of the (David Hilbert formal
> proof from a pair of input finite strings to a pair of final states
> within the language of Turing Machine Descriptions) debug trace.

	Loops of form "WHILE f(n) DO n := n+1 OD" don't lack termination
conditions, but may or may not loop indefinitely.  At what point will
your emulation decide that it has looped enough and determine that the
loop will never terminate?  Simple variants of that loop may be used to
resolve the Goldbach conjecture or the Collatz conjecture [and it is
well-known that many Collatz-like conjectures are undecidable -- see
Lagarias's book "The Ultimate Challenge"].

-- 
Andy Walker,
Nottingham.

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


Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | sci.logic


csiph-web