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


Groups > sci.logic > #172316 > unrolled thread

Re: Necessary sequence of halt decider's inference chain

Started bygrahamcooper7@gmail.com
First post2018-02-09 22:20 -0800
Last post2018-02-11 01:38 +0000
Articles 9 — 3 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: Necessary sequence of halt decider's inference chain grahamcooper7@gmail.com - 2018-02-09 22:20 -0800
    Re: Necessary sequence of halt decider's inference chain Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-10 12:28 +0000
      Re: Necessary sequence of halt decider's inference chain Pete Olcott <Pete@NoEmail.address> - 2018-02-10 09:15 -0600
        Re: Necessary sequence of halt decider's inference chain Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-10 16:44 +0000
          Re: Necessary sequence of halt decider's inference chain grahamcooper7@gmail.com - 2018-02-10 15:16 -0800
      Re: Necessary sequence of halt decider's inference chain grahamcooper7@gmail.com - 2018-02-10 15:27 -0800
        Re: Necessary sequence of halt decider's inference chain Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-11 00:20 +0000
          Re: Necessary sequence of halt decider's inference chain grahamcooper7@gmail.com - 2018-02-10 17:21 -0800
            Re: Necessary sequence of halt decider's inference chain Ben Bacarisse <ben.usenet@bsb.me.uk> - 2018-02-11 01:38 +0000

#172316 — Re: Necessary sequence of halt decider's inference chain

Fromgrahamcooper7@gmail.com
Date2018-02-09 22:20 -0800
SubjectRe: Necessary sequence of halt decider's inference chain
Message-ID<959bc654-e795-41a3-827f-fb0378bf7beb@googlegroups.com>
On Saturday, February 10, 2018 at 1:34:11 AM UTC+10, Pete Olcott wrote:
> http://www.liarparadox.org/H_evaluates_S.pdf
>         
> 
>       
>     This
>         is the text from the PDF. It is much more easily understood
> 
>     when
>         the state transition diagrams can be seen. 
> 
>         
> 
>         Understanding 
>     this
>         is a necessary prerequisite to understanding 
> 
>         how H Ĥx Ĥx would
>               be evaluated. Ĥx is constructed using H as its basis. 
>     
> 
>     
> 
>     Definition
>               of Turing Machine Ĥx 
>     
> 
>     q0
>             Wm ⊢* Ĥx qx Wm Wm ⊢* Ĥx qy 
>     
> 
>     q0
>             Wm ⊢* Ĥx qx Wm Wm ⊢* Ĥx qn
> 
>     
> 
>     The
>         squiggly lines proceeding from state (q0) are represented in
>         text as
>         the asterisk * wildcard ⊢
> 
>     character.
>         These conventions are used to encode unspecified state
>         transition
>         sequences.
> 
>     
> 
>     Definition
>             of Turing Machine H (state transition sequence)
> 
>     q0
>         Wm W * H qy 
>     
> 
>     q0
>         Wm W * H qn 
>     
> 
>     
> 
>     The
>         diagram and the state transition sequence indicate that H begins
>         at
>         its own start state and is
> 
>     applied
>         to TM description Wm with input W.
> 
>     
> 
>     The
>         Final state ((qy)) indicates that Turing Machine wM will halt on
>         its
>         input w (halts = yes).
> 
>     The
>         Final state ((qn)) indicates that Turing Machine wM will not
>         halt on
>         its input w (halts = no).
> 
>     
> 
>     Definition
>             of Turing Machine S (state transition sequence)
> 
>     q0
>         W ⊢* S qy ∞
> 
>     q0
>         W ⊢”E” S q1 ⊢”N” S q2 ⊢”D” S qn
> 
>     
> 
>     Turing
>         Machine S begins at start state q0
> 
>     S
>         transitions from q0 to q1 on “E” else qy ∞
> 
>     S
>         transitions from q1 to q2 on “N” else qy ∞
> 
>     S
>         transitions from q2 to q3 on “D” else qy ∞
> 
>     
> 
>     What
>             is the necessary sequence of the inference chain for halt
>             decider H
>             to decide: S “ENN” ? 
>     



Halt is not a LANGUAGE decider, it is a PROGRAM decider.


You dont put


----------------------------
00000000END00000000000
----------------------------


on the TURING TAPE and compute "YES" its in the LANGUAGE of ALLOWED STRINGS!



Nope!

a FINITE STATE MACHINE can do that!   NO TAPE NEEDED!




JUST USE EBNF



INPUT ::- INPUT INPUT
INPUT ::- e
INPUT ::- n
INPUT ::- d


It will parse all sentences in L using terminal symbols 'e' 'n' 'd' in any order

[toc] | [next] | [standalone]


#172322

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2018-02-10 12:28 +0000
Message-ID<87y3k1ni4w.fsf@bsb.me.uk>
In reply to#172316
grahamcooper7@gmail.com writes:
<snip>
> Halt is not a LANGUAGE decider, it is a PROGRAM decider.

I don't usually reply to your posts because I can't understand the
fractured comments, but this one looks plain wrong.  All deciders are
language deciders.  A halt decider is a decider for the language
(i.e. set of strings) that encode halting TM computations.

Posters here often play Humpty Dumpty with technical terms, but that
does not make them right.

-- 
Ben.

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


#172338

FromPete Olcott <Pete@NoEmail.address>
Date2018-02-10 09:15 -0600
Message-ID<r8udnZXUH97lkeLHnZ2dnUU7-UXNnZ2d@giganews.com>
In reply to#172322
On 2/10/2018 6:28 AM, Ben Bacarisse wrote:
> grahamcooper7@gmail.com writes:
> <snip>
>> Halt is not a LANGUAGE decider, it is a PROGRAM decider.
> 
> I don't usually reply to your posts because I can't understand the
> fractured comments, but this one looks plain wrong.  All deciders are
> language deciders.  A halt decider is a decider for the language
> (i.e. set of strings) that encode halting TM computations.
> 

Yes and furthermore the halt decider evaluates its input as a syntactic
logical consequence (formal proof) in the language of Turing Machine
Descriptions from a finite string pair to its final states of H.qy or H.qn.

The decision answers this question:
Does the finite string pair represent a correct TM that would halt on its input?

A transition to H.qn means
(1) Not a TM
(2) Not a correct TM
(3) A Correct TM that would not halt


> Posters here often play Humpty Dumpty with technical terms, but that
> does not make them right.
> 


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

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


#172342

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2018-02-10 16:44 +0000
Message-ID<877erkoku0.fsf@bsb.me.uk>
In reply to#172338
Pete Olcott <Pete@NoEmail.address> writes:

> On 2/10/2018 6:28 AM, Ben Bacarisse wrote:
>> grahamcooper7@gmail.com writes:
>> <snip>
>>> Halt is not a LANGUAGE decider, it is a PROGRAM decider.
>>
>> I don't usually reply to your posts because I can't understand the
>> fractured comments, but this one looks plain wrong.  All deciders are
>> language deciders.  A halt decider is a decider for the language
>> (i.e. set of strings) that encode halting TM computations.
>
> Yes and furthermore the halt decider evaluates its input as a syntactic
> logical consequence (formal proof) in the language of Turing Machine
> Descriptions from a finite string pair to its final states of H.qy or
> H.qn.

Who knows?  One day you might decide to write that in terms that you
have not made up.

A halt decider must determine the halting or otherwise of the input.  If
that is what "evaluates its input as a syntactic logical consequence
(formal proof) in the language of Turing Machine Descriptions from a
finite string pair to its final states of H.qy or H.qn" means then you
are correct.  If those words are the ones that allow you to deny that H
always transitions from H.q0 to either H.qy or H.qn then you are wrong.

Asking cranks to decode the made up language they use to hide what they
means is almost always a waste of time.  You are either right, and the
proof follows immediately, or you are wrong.  100 more posts trying to
get you explain which is the seems like a daunting prospect.

> The decision answers this question:
> Does the finite string pair represent a correct TM that would halt on
> its input?

Hey, yes, a correct remark!

> A transition to H.qn means
> (1) Not a TM
> (2) Not a correct TM
> (3) A Correct TM that would not halt

Yes!  Now explain H.qy and attach those remarks to the lines you keep
writing (and not understanding) you will have the start of the proof --
the specification of H.  It's a bit wordy, but it's progress.

-- 
Ben.

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


#172376

Fromgrahamcooper7@gmail.com
Date2018-02-10 15:16 -0800
Message-ID<4cd7f4fa-bf41-4275-a92b-03bb49a7a9f4@googlegroups.com>
In reply to#172342
On Sunday, Ben Bacarisse wrote:
> Pete Olcott <Pete@NoEmail.address> writes:

> > The decision answers this question:
> > Does the finite string pair represent a correct TM that would halt on
> > its input?
> 
> Hey, yes, a correct remark!


Rubbish!

Define INCORRECT TM!



> 
> > A transition to H.qn means
> > (1) Not a TM
> > (2) Not a correct TM
> > (3) A Correct TM that would not halt
> 
> Yes!  Now explain H.qy and attach those remarks to the lines you keep
> writing (and not understanding) you will have the start of the proof --
> the specification of H.  It's a bit wordy, but it's progress.


STUPID!

A NOT_CORRECT TM (your terms) simply halts (but has some other "correctness" desiderata, eg. an infinite evaluation loop (Pete's term))

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


#172377

Fromgrahamcooper7@gmail.com
Date2018-02-10 15:27 -0800
Message-ID<95384b56-12f1-4ef8-9bc1-9429b825b1d4@googlegroups.com>
In reply to#172322
On Saturday, February 10, 2018 at 10:28:33 PM UTC+10, Ben Bacarisse wrote:
> grahamcooper7@gmail.com writes:
> <snip>
> > Halt is not a LANGUAGE decider, it is a PROGRAM decider.
> 
> I don't usually reply to your posts because I can't understand the
> fractured comments, but this one looks plain wrong.  All deciders are
> language deciders.  A halt decider is a decider for the language
> (i.e. set of strings) that encode halting TM computations.
> 
> Posters here often play Humpty Dumpty with technical terms, but that
> does not make them right.



No a LANGUAGE DECIDER is computable.


https://en.wikipedia.org/wiki/Recursive_language


A recursive language is a formal language for which there exists a Turing machine that, when presented with any finite input string, halts and accepts if the string is in the language, and halts and rejects otherwise. The Turing machine always halts: it is known as a decider and is said to decide the recursive language.

By the second definition, any decision problem can be shown to be decidable by exhibiting an algorithm for it that terminates on all inputs. An undecidable problem is a problem that is not decidable.

Examples[edit]

As noted above, every context-sensitive language is recursive. Thus, a simple example of a recursive language is the set L={abc, aabbcc, aaabbbccc, ...}; more formally, the set

L = {  w in { a , b , c } ∗   ∣ w = a n2   b n3   c n4    for some    n >= 1  }  



Did you even CLICK on Pete's PDF file.... he's using TM state transitions to interpret non-binary symbols.


OP

http://www.liarparadox.org/H_evaluates_S.pdf 

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


#172379

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2018-02-11 00:20 +0000
Message-ID<873728l6li.fsf@bsb.me.uk>
In reply to#172377
grahamcooper7@gmail.com writes:

> On Saturday, February 10, 2018 at 10:28:33 PM UTC+10, Ben Bacarisse wrote:
>> grahamcooper7@gmail.com writes:
>> <snip>
>> > Halt is not a LANGUAGE decider, it is a PROGRAM decider.
>> 
>> I don't usually reply to your posts because I can't understand the
>> fractured comments, but this one looks plain wrong.  All deciders are
>> language deciders.  A halt decider is a decider for the language
>> (i.e. set of strings) that encode halting TM computations.
>> 
>> Posters here often play Humpty Dumpty with technical terms, but that
>> does not make them right.
>
> No a LANGUAGE DECIDER is computable.

Not all languages are decidable,

> https://en.wikipedia.org/wiki/Recursive_language

as the text at that link correctly sates.

-- 
Ben.

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


#172380

Fromgrahamcooper7@gmail.com
Date2018-02-10 17:21 -0800
Message-ID<462d45a8-b558-4365-b0b6-52ed7dfe9888@googlegroups.com>
In reply to#172379
On Sunday, February 11, 2018 at 10:20:45 AM UTC+10, Ben Bacarisse wrote:
> grahamcooper7@gmail.com writes:
> 
> > On Saturday, February 10, 2018 at 10:28:33 PM UTC+10, Ben Bacarisse wrote:
> >> grahamcooper7@gmail.com writes:
> >> <snip>
> >> > Halt is not a LANGUAGE decider, it is a PROGRAM decider.
> >> 
> >> I don't usually reply to your posts because I can't understand the
> >> fractured comments, but this one looks plain wrong.  All deciders are
> >> language deciders.  A halt decider is a decider for the language
> >> (i.e. set of strings) that encode halting TM computations.
> >> 
> >> Posters here often play Humpty Dumpty with technical terms, but that
> >> does not make them right.
> >
> > No a LANGUAGE DECIDER is computable.
> 
> Not all languages are decidable,
> 
> > https://en.wikipedia.org/wiki/Recursive_language
> 
> as the text at that link correctly sates.



Which of these is TRUE?

1/ HALT IS A DECIDER
2/ HALT IS NOT A DECIDER



there exists a Turing machine that, when presented with any finite input string, halts and accepts if the string is in the language

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


#172381

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2018-02-11 01:38 +0000
Message-ID<87r2psjof9.fsf@bsb.me.uk>
In reply to#172380
grahamcooper7@gmail.com writes:

> On Sunday, February 11, 2018 at 10:20:45 AM UTC+10, Ben Bacarisse wrote:
>> grahamcooper7@gmail.com writes:
>> 
>> > On Saturday, February 10, 2018 at 10:28:33 PM UTC+10, Ben Bacarisse wrote:
>> >> grahamcooper7@gmail.com writes:
>> >> <snip>
>> >> > Halt is not a LANGUAGE decider, it is a PROGRAM decider.
>> >> 
>> >> I don't usually reply to your posts because I can't understand the
>> >> fractured comments, but this one looks plain wrong.  All deciders are
>> >> language deciders.  A halt decider is a decider for the language
>> >> (i.e. set of strings) that encode halting TM computations.
>> >> 
>> >> Posters here often play Humpty Dumpty with technical terms, but that
>> >> does not make them right.
>> >
>> > No a LANGUAGE DECIDER is computable.
>> 
>> Not all languages are decidable,
>> 
>> > https://en.wikipedia.org/wiki/Recursive_language
>> 
>> as the text at that link correctly sates.
>
> Which of these is TRUE?
>
> 1/ HALT IS A DECIDER
> 2/ HALT IS NOT A DECIDER
  3/ HALT IS JUST A NAME
  4/ WHAT'S HALT?
  5/ DO I HAVE TO GUESS?

> there exists a Turing machine that, when presented with any finite
> input string, halts and accepts if the string is in the language

for any recursively enumerable (AKA semi-decidable) language, yes.

-- 
Ben.

[toc] | [prev] | [standalone]


Back to top | Article view | sci.logic


csiph-web