Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > sci.logic > #172316 > unrolled thread
| Started by | grahamcooper7@gmail.com |
|---|---|
| First post | 2018-02-09 22:20 -0800 |
| Last post | 2018-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.
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
| From | grahamcooper7@gmail.com |
|---|---|
| Date | 2018-02-09 22:20 -0800 |
| Subject | Re: 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]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2018-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]
| From | Pete Olcott <Pete@NoEmail.address> |
|---|---|
| Date | 2018-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]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2018-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]
| From | grahamcooper7@gmail.com |
|---|---|
| Date | 2018-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]
| From | grahamcooper7@gmail.com |
|---|---|
| Date | 2018-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]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2018-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]
| From | grahamcooper7@gmail.com |
|---|---|
| Date | 2018-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]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2018-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