Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.theory > #32496 > unrolled thread
| Started by | olcott <NoOne@NoWhere.com> |
|---|---|
| First post | 2021-05-01 11:30 -0500 |
| Last post | 2021-05-02 21:46 +0100 |
| Articles | 12 on this page of 92 — 7 participants |
Back to article view | Back to comp.theory
Mutual agreement on the definition of a [computation] in computer science olcott <NoOne@NoWhere.com> - 2021-05-01 11:30 -0500
Re: Mutual agreement on the definition of a [computation] in computer science olcott <NoOne@NoWhere.com> - 2021-05-01 11:37 -0500
Re: Mutual agreement on the definition of a [computation] in computer science olcott <NoOne@NoWhere.com> - 2021-05-01 12:40 -0500
Re: Mutual agreement on the definition of a [computation] in computer science Richard Damon <Richard@Damon-Family.org> - 2021-05-01 14:55 -0400
Re: Mutual agreement on the definition of a [computation] in computer science olcott <NoOne@NoWhere.com> - 2021-05-01 14:09 -0500
Re: Mutual agreement on the definition of a [computation] in computer science Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk> - 2021-05-01 22:42 +0100
Re: Mutual agreement on the definition of a [computation] in computer science olcott <NoOne@NoWhere.com> - 2021-05-01 17:32 -0500
Re: Mutual agreement on the definition of a [computation] in computer science Richard Damon <Richard@Damon-Family.org> - 2021-05-01 18:43 -0400
Re: Mutual agreement on the definition of a [computation] in computer science olcott <NoOne@NoWhere.com> - 2021-05-01 18:16 -0500
Re: Mutual agreement on the definition of a [computation] in computer science Richard Damon <Richard@Damon-Family.org> - 2021-05-01 21:20 -0400
Re: Mutual agreement on the definition of a [computation] in computer science Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk> - 2021-05-02 00:49 +0100
Re: Mutual agreement on the definition of a [computation] in computer science Richard Damon <Richard@Damon-Family.org> - 2021-05-01 18:02 -0400
Re: Mutual agreement on the definition of a [computation] in computer science olcott <NoOne@NoWhere.com> - 2021-05-01 17:49 -0500
Re: Mutual agreement on the definition of a [computation] in computer science André G. Isaak <agisaak@gm.invalid> - 2021-05-01 17:28 -0600
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-01 18:42 -0500
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-02 01:51 +0100
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-01 20:05 -0500
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-02 02:20 +0100
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-01 20:42 -0500
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-01 22:10 -0400
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-02 03:30 +0100
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-01 23:36 -0500
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-02 07:51 -0400
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-02 21:38 +0100
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-02 17:11 -0400
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-03 00:53 +0100
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-02 19:45 -0500
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-02 20:56 -0400
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-02 20:55 -0400
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-03 13:43 +0100
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-03 09:06 -0500
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-03 10:34 -0400
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-04 00:58 +0100
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-04 10:12 -0500
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-04 21:57 +0100
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Jeff Barnett <jbb@notatt.com> - 2021-05-03 11:39 -0600
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-02 17:41 -0500
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-03 00:52 +0100
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-02 19:34 -0500
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-02 20:49 -0400
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-03 17:23 +0100
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-03 14:00 -0500
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-03 15:23 -0400
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-04 09:53 -0500
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-04 11:21 -0400
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-04 10:28 -0500
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-04 11:40 -0400
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-04 17:11 +0100
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-04 11:23 -0500
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-04 12:40 -0400
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-04 11:46 -0500
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-04 13:17 -0400
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-04 21:47 +0100
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-04 17:31 -0400
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-04 23:21 +0100
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-04 00:49 +0100
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-04 10:09 -0500
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-04 10:45 -0500
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-04 19:50 +0100
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-04 10:04 -0500
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-04 11:22 -0400
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-04 10:31 -0500
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-04 11:46 -0400
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-04 19:56 +0100
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-02 20:44 -0400
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] André G. Isaak <agisaak@gm.invalid> - 2021-05-01 21:14 -0600
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-02 00:04 -0500
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] André G. Isaak <agisaak@gm.invalid> - 2021-05-01 23:27 -0600
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] olcott <NoOne@NoWhere.com> - 2021-05-02 12:47 -0500
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-02 14:38 -0400
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-01 21:40 -0400
Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ] Richard Damon <Richard@Damon-Family.org> - 2021-05-01 21:35 -0400
Re: Mutual agreement on the definition of a [computation] in computer science Richard Damon <Richard@Damon-Family.org> - 2021-05-01 21:29 -0400
Re: Mutual agreement on the definition of a [computation] in computer science Richard Damon <Richard@Damon-Family.org> - 2021-05-01 14:49 -0400
Re: Mutual agreement on the definition of a [computation] in computer science olcott <NoOne@NoWhere.com> - 2021-05-01 14:02 -0500
Re: Mutual agreement on the definition of a [computation] in computer science Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-01 22:50 +0100
Re: Mutual agreement on the definition of a [computation] in computer science Kaz Kylheku <563-365-8930@kylheku.com> - 2021-05-01 18:22 +0000
Re: Mutual agreement on the definition of a [computation] in computer science olcott <NoOne@NoWhere.com> - 2021-05-01 13:35 -0500
Re: Mutual agreement on the definition of a [computation] in computer science Mr Flibble <flibble@i42.REMOVETHISBIT.co.uk> - 2021-05-01 22:39 +0100
Re: Mutual agreement on the definition of a [computation] in computer science Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-01 22:49 +0100
Re: Mutual agreement on the definition of a [computation] in computer science olcott <NoOne@NoWhere.com> - 2021-05-01 18:35 -0500
Re: Mutual agreement on the definition of a [computation] in computer science Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-02 01:56 +0100
Re: Mutual agreement on the definition of a [computation] in computer science olcott <NoOne@NoWhere.com> - 2021-05-01 20:22 -0500
Re: Mutual agreement on the definition of a [computation] in computer science Richard Damon <Richard@Damon-Family.org> - 2021-05-01 21:45 -0400
Re: Mutual agreement on the definition of a [computation] in computer science Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-02 02:53 +0100
Re: Mutual agreement on the definition of a [computation] in computer science olcott <NoOne@NoWhere.com> - 2021-05-01 23:55 -0500
Re: Mutual agreement on the definition of a [computation] in computer science André G. Isaak <agisaak@gm.invalid> - 2021-05-01 23:07 -0600
Re: Mutual agreement on the definition of a [computation] in computer science Richard Damon <Richard@Damon-Family.org> - 2021-05-02 08:10 -0400
Re: Mutual agreement on the definition of a [computation] in computer science Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-02 20:29 +0100
Re: Mutual agreement on the definition of a [computation] in computer science olcott <NoOne@NoWhere.com> - 2021-05-02 14:34 -0500
Re: Mutual agreement on the definition of a [computation] in computer science Richard Damon <Richard@Damon-Family.org> - 2021-05-02 15:48 -0400
Re: Mutual agreement on the definition of a [computation] in computer science Ben Bacarisse <ben.usenet@bsb.me.uk> - 2021-05-02 21:46 +0100
Page 5 of 5 — ← Prev page 1 2 3 4 [5]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-05-01 18:35 -0500 |
| Message-ID | <QsednVs36qATeBD9nZ2dnUU7-XXNnZ2d@giganews.com> |
| In reply to | #32518 |
On 5/1/2021 4:49 PM, Ben Bacarisse wrote: > olcott <NoOne@NoWhere.com> writes: > >> There seems to be little agreement on the precise details of what is >> and what is not a computation in computer science across respondents >> here and textbook definitions. > > No. /You/ may me confused by slightly different definitions, but there > is no substantive disagreement on this matter. > >> Since the input finite string can possibly be empty a Turing machine M >> that simply transitions from its start state to its final state would >> be a computable function. > > Category error. > I had all three textbook definitions handy in the first link and tried to correct my category error in the last paragraph. The most significant difference of the textbook definitions is that Sipser seems to think that a TM must erase its input. The difference between Linz and the others regarding the nature of the input is a matter of abstraction. Linz speaks about it more from the mathematical perspective as outlined here (what is being represented) https://math.stackexchange.com/questions/2993807/what-is-a-computable-function Sipser and Kozen are speaking of it from a computer science perspective. Even the elements of the Domain are still represented as finite strings from the input alphabet. The textbooks seem to be pretty close. When respondents here talk about disallowed side-effects they greatly diverge from the actual theory of computation and digress into software engineering. My intention is to have this equally apply to TMs and x86 programs: A [computation] is some sequence of mechanical steps that begins at a start state (initial configuration) and ends in some specific final state (final configuration) on some possibly empty input finite string. An optional finite string output is construed as an aspect of the final configuration. -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-05-02 01:56 +0100 |
| Message-ID | <87o8du9cnv.fsf@bsb.me.uk> |
| In reply to | #32532 |
olcott <NoOne@NoWhere.com> writes: > On 5/1/2021 4:49 PM, Ben Bacarisse wrote: >> olcott <NoOne@NoWhere.com> writes: >> >>> There seems to be little agreement on the precise details of what is >>> and what is not a computation in computer science across respondents >>> here and textbook definitions. >> >> No. /You/ may me confused by slightly different definitions, but there >> is no substantive disagreement on this matter. >> >>> Since the input finite string can possibly be empty a Turing machine M >>> that simply transitions from its start state to its final state would >>> be a computable function. >> >> Category error. > > I had all three textbook definitions handy in the first link and tried > to correct my category error in the last paragraph. You /made/ the category error in the last paragraph. A TM can not be a computable function. The TM you describe computes the identity function. > The most significant difference of the textbook definitions is that > Sipser seems to think that a TM must erase its input. I knew you were confused, but I did not know you were this confused. > The textbooks seem to be pretty close. When respondents here talk > about disallowed side-effects they greatly diverge from the actual > theory of computation and digress into software engineering. They are trying to stop you playing silly games with your informal, hacked up, "model" of computation. It is you that have abandoned the theory and are grubbing about with x86 code and mysterious hidden C functions. With a proper model, the whole issue vanishes. TMs don't have side-effects and properly constructed programs (no functions), written in any formal notation of your choice, wouldn't have side-effects either. It is your examples that use your messed up informal model that need to be kept on the straight and narrow about side-effects. > My intention is to have this equally apply to TMs and x86 programs: > A [computation] is some sequence of mechanical steps that begins at a > start state (initial configuration) and ends in some specific final > state (final configuration) on some possibly empty input finite > string. It is not true of TMs (unless you are changing how the term "computation" has been used for months in these threads), but it is not even wrong about x86 programs. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-05-01 20:22 -0500 |
| Message-ID | <yvednXcPGP40YxD9nZ2dnUU7-aPNnZ2d@giganews.com> |
| In reply to | #32537 |
On 5/1/2021 7:56 PM, Ben Bacarisse wrote: > olcott <NoOne@NoWhere.com> writes: > >> On 5/1/2021 4:49 PM, Ben Bacarisse wrote: >>> olcott <NoOne@NoWhere.com> writes: >>> >>>> There seems to be little agreement on the precise details of what is >>>> and what is not a computation in computer science across respondents >>>> here and textbook definitions. >>> >>> No. /You/ may me confused by slightly different definitions, but there >>> is no substantive disagreement on this matter. >>> >>>> Since the input finite string can possibly be empty a Turing machine M >>>> that simply transitions from its start state to its final state would >>>> be a computable function. >>> >>> Category error. >> >> I had all three textbook definitions handy in the first link and tried >> to correct my category error in the last paragraph. > > You /made/ the category error in the last paragraph. A TM can not be a > computable function. The TM you describe computes the identity function. > >> The most significant difference of the textbook definitions is that >> Sipser seems to think that a TM must erase its input. > > I knew you were confused, but I did not know you were this confused. > Definition 5.12 A function f: Σ* → Σ* is a computable function if some Turing machine M, on every input w, halts with just f(w) on its tape. If only f(w) is on its tape that means that w is <not> on its tape. The function of an input is <only> its output. So maybe I should have "interpreted" [just f(w) on its tape] to mean Not[just f(w) on its tape] ??? >> The textbooks seem to be pretty close. When respondents here talk >> about disallowed side-effects they greatly diverge from the actual >> theory of computation and digress into software engineering. > > They are trying to stop you playing silly games with your informal, > hacked up, "model" of computation. It is you that have abandoned the > theory and are grubbing about with x86 code and mysterious hidden C > functions. > > With a proper model, the whole issue vanishes. TMs don't have > side-effects I knew that this was impossible. Not everyone here knows that. > and properly constructed programs (no functions), written > in any formal notation of your choice, wouldn't have side-effects > either. It is your examples that use your messed up informal model that > need to be kept on the straight and narrow about side-effects. I never brought up the issue of side-effects. It has nothing to do with the theory of computation. Horribly awful software engineering can be simulated on a TM. To begin with TM are inherently spaghetti code. > >> My intention is to have this equally apply to TMs and x86 programs: >> A [computation] is some sequence of mechanical steps that begins at a >> start state (initial configuration) and ends in some specific final >> state (final configuration) on some possibly empty input finite >> string. > > It is not true of TMs (unless you are changing how the term > "computation" has been used for months in these threads), but it is not > even wrong about x86 programs. > What is the most correct, succinct way to say it? -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2021-05-01 21:45 -0400 |
| Message-ID | <mvnjI.23025$zx1.18680@fx20.iad> |
| In reply to | #32542 |
On 5/1/21 9:22 PM, olcott wrote: > On 5/1/2021 7:56 PM, Ben Bacarisse wrote: >> olcott <NoOne@NoWhere.com> writes: >> >>> On 5/1/2021 4:49 PM, Ben Bacarisse wrote: >>>> olcott <NoOne@NoWhere.com> writes: >>>> >>>>> There seems to be little agreement on the precise details of what is >>>>> and what is not a computation in computer science across respondents >>>>> here and textbook definitions. >>>> >>>> No. /You/ may me confused by slightly different definitions, but there >>>> is no substantive disagreement on this matter. >>>> >>>>> Since the input finite string can possibly be empty a Turing machine M >>>>> that simply transitions from its start state to its final state would >>>>> be a computable function. >>>> >>>> Category error. >>> >>> I had all three textbook definitions handy in the first link and tried >>> to correct my category error in the last paragraph. >> >> You /made/ the category error in the last paragraph. A TM can not be a >> computable function. The TM you describe computes the identity function. >> >>> The most significant difference of the textbook definitions is that >>> Sipser seems to think that a TM must erase its input. >> >> I knew you were confused, but I did not know you were this confused. >> > > Definition 5.12 > A function f: Σ* → Σ* is a computable function if some Turing machine M, > on every input w, halts with just f(w) on its tape. The Category Error is that the function f is a mapping. The Turing Machine is an algorithm. The Turing Machine could be said to COMPUTE the function, but it isn't the function itself. Like the function sin(x) on your computer. It computes values of the sin function, but it isn't the function itself. You can't 'square' the code itself, and add it to the 'square' of the code for cos and get 1. You can do that operation of the particular values you get from it. >
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-05-02 02:53 +0100 |
| Message-ID | <87czu9aoke.fsf@bsb.me.uk> |
| In reply to | #32542 |
olcott <NoOne@NoWhere.com> writes: > On 5/1/2021 7:56 PM, Ben Bacarisse wrote: >> olcott <NoOne@NoWhere.com> writes: >> >>> On 5/1/2021 4:49 PM, Ben Bacarisse wrote: >>>> olcott <NoOne@NoWhere.com> writes: >>>> >>>>> There seems to be little agreement on the precise details of what is >>>>> and what is not a computation in computer science across respondents >>>>> here and textbook definitions. >>>> >>>> No. /You/ may me confused by slightly different definitions, but there >>>> is no substantive disagreement on this matter. >>>> >>>>> Since the input finite string can possibly be empty a Turing machine M >>>>> that simply transitions from its start state to its final state would >>>>> be a computable function. >>>> >>>> Category error. >>> >>> I had all three textbook definitions handy in the first link and tried >>> to correct my category error in the last paragraph. >> >> You /made/ the category error in the last paragraph. A TM can not be a >> computable function. The TM you describe computes the identity function. >> >>> The most significant difference of the textbook definitions is that >>> Sipser seems to think that a TM must erase its input. >> >> I knew you were confused, but I did not know you were this confused. > > Definition 5.12 > A function f: Σ* → Σ* is a computable function if some Turing machine > M, on every input w, halts with just f(w) on its tape. > > If only f(w) is on its tape that means that w is <not> on its tape. > The function of an input is <only> its output. > > So maybe I should have "interpreted" [just f(w) on its tape] to > mean Not[just f(w) on its tape] ??? No, your interpretation is correct. The quickest way to find out what I think you are confused by would be to ask me. Speculating on what I mean has a very low success rate for you. Had you asked, I'd have said you are confused in thinking Siper's definition is different in this regard. As it happens, Siper's is the odd one out, but for a totally different reason. >>> The textbooks seem to be pretty close. When respondents here talk >>> about disallowed side-effects they greatly diverge from the actual >>> theory of computation and digress into software engineering. >> >> They are trying to stop you playing silly games with your informal, >> hacked up, "model" of computation. It is you that have abandoned the >> theory and are grubbing about with x86 code and mysterious hidden C >> functions. >> >> With a proper model, the whole issue vanishes. TMs don't have >> side-effects > > I knew that this was impossible. Not everyone here knows that. That depends on "here". I see you have fished in the C and C++ ponds again and hooked someone who does not know the subject well. I don't think anyone you have been talking to regularly "here" (comp.theory) is in any doubt about it. >> and properly constructed programs (no functions), written >> in any formal notation of your choice, wouldn't have side-effects >> either. It is your examples that use your messed up informal model that >> need to be kept on the straight and narrow about side-effects. > > I never brought up the issue of side-effects. It has nothing to do > with the theory of computation. You brought the subject up by describing Halts in terms that can only be explained by cheating using side-effects. Of course, you are still hiding the code, and by the time you publish anything, you may have found a way to remove the behaviour you have described to us. >>> My intention is to have this equally apply to TMs and x86 programs: >>> A [computation] is some sequence of mechanical steps that begins at a >>> start state (initial configuration) and ends in some specific final >>> state (final configuration) on some possibly empty input finite >>> string. Do you think that Turing machine states and machine configuration are the same thing? The use of clarifying (explanatory) parentheses hints at it. >> It is not true of TMs (unless you are changing how the term >> "computation" has been used for months in these threads), but it is not >> even wrong about x86 programs. > > What is the most correct, succinct way to say it? A computation is the sequence of configurations generated by the state transition function of a TM and an initial input string. This sequence is either finite or infinite. The most succinct way to expand on this (some of these are technical terms) would make use of a simpler definition of a Turing machine without any final states, but that would probably make you think I was mad. I would not try to say anything like this about x86 programs. They are not properly defined, not Turing complete and don't constitute a model of computation suitable for theoretical investigations. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-05-01 23:55 -0500 |
| Message-ID | <17GdnTG13PMorRP9nZ2dnUU7-fvNnZ2d@giganews.com> |
| In reply to | #32548 |
On 5/1/2021 8:53 PM, Ben Bacarisse wrote: > olcott <NoOne@NoWhere.com> writes: > >> On 5/1/2021 7:56 PM, Ben Bacarisse wrote: >>> olcott <NoOne@NoWhere.com> writes: >>> >>>> On 5/1/2021 4:49 PM, Ben Bacarisse wrote: >>>>> olcott <NoOne@NoWhere.com> writes: >>>>> >>>>>> There seems to be little agreement on the precise details of what is >>>>>> and what is not a computation in computer science across respondents >>>>>> here and textbook definitions. >>>>> >>>>> No. /You/ may me confused by slightly different definitions, but there >>>>> is no substantive disagreement on this matter. >>>>> >>>>>> Since the input finite string can possibly be empty a Turing machine M >>>>>> that simply transitions from its start state to its final state would >>>>>> be a computable function. >>>>> >>>>> Category error. >>>> >>>> I had all three textbook definitions handy in the first link and tried >>>> to correct my category error in the last paragraph. >>> >>> You /made/ the category error in the last paragraph. A TM can not be a >>> computable function. The TM you describe computes the identity function. >>> >>>> The most significant difference of the textbook definitions is that >>>> Sipser seems to think that a TM must erase its input. >>> >>> I knew you were confused, but I did not know you were this confused. >> >> Definition 5.12 >> A function f: Σ* → Σ* is a computable function if some Turing machine >> M, on every input w, halts with just f(w) on its tape. >> >> If only f(w) is on its tape that means that w is <not> on its tape. >> The function of an input is <only> its output. >> >> So maybe I should have "interpreted" [just f(w) on its tape] to >> mean Not[just f(w) on its tape] ??? > > No, your interpretation is correct. > > The quickest way to find out what I think you are confused by would be > to ask me. Speculating on what I mean has a very low success rate for > you. Had you asked, I'd have said you are confused in thinking Siper's > definition is different in this regard. > > As it happens, Siper's is the odd one out, but for a totally different > reason. > >>>> The textbooks seem to be pretty close. When respondents here talk >>>> about disallowed side-effects they greatly diverge from the actual >>>> theory of computation and digress into software engineering. >>> >>> They are trying to stop you playing silly games with your informal, >>> hacked up, "model" of computation. It is you that have abandoned the >>> theory and are grubbing about with x86 code and mysterious hidden C >>> functions. >>> >>> With a proper model, the whole issue vanishes. TMs don't have >>> side-effects >> >> I knew that this was impossible. Not everyone here knows that. > > That depends on "here". I see you have fished in the C and C++ ponds > again and hooked someone who does not know the subject well. I don't > think anyone you have been talking to regularly "here" (comp.theory) is > in any doubt about it. > >>> and properly constructed programs (no functions), written >>> in any formal notation of your choice, wouldn't have side-effects >>> either. It is your examples that use your messed up informal model that >>> need to be kept on the straight and narrow about side-effects. >> >> I never brought up the issue of side-effects. It has nothing to do >> with the theory of computation. > > You brought the subject up by describing Halts in terms that can only be > explained by cheating using side-effects. None of the theory of comutation texts say anything like this. There cannot actually be anything like a cheating side effect. I dare you to cite any theory of computation source that says anything about chreating side effects. A TM does whatever a TM does as long as it transforms an input finite string into a final state it is free to do anything else inbetween without the possibility of cheating side effects because TMs are incapable of cheating and any side-effects are part of the computation. > Of course, you are still > hiding the code, and by the time you publish anything, you may have > found a way to remove the behaviour you have described to us. You have to accept the code before you see it on the basis of its design. If you are incapable of doing that then you are unqualified to evaluate it. >>>> My intention is to have this equally apply to TMs and x86 programs: >>>> A [computation] is some sequence of mechanical steps that begins at a >>>> start state (initial configuration) and ends in some specific final >>>> state (final configuration) on some possibly empty input finite >>>> string. > > Do you think that Turing machine states and machine configuration are > the same thing? The use of clarifying (explanatory) parentheses hints > at it. > When use generically the whole state of a machine is the value of every memory location. When applied to TMs is has a more specific meaning. >>> It is not true of TMs (unless you are changing how the term >>> "computation" has been used for months in these threads), but it is not >>> even wrong about x86 programs. >> >> What is the most correct, succinct way to say it? > > A computation is the sequence of configurations generated by the state > transition function of a TM and an initial input string. This sequence > is either finite or infinite. That sound pretty good now can be make it generic across every model of computation? The initial state of an x86 machine is the value of each memory location, the value of each register. The final state is the same thing. > > The most succinct way to expand on this (some of these are technical > terms) would make use of a simpler definition of a Turing machine > without any final states, but that would probably make you think I was > mad. > > I would not try to say anything like this about x86 programs. They are > not properly defined, not Turing complete and don't constitute a model > of computation suitable for theoretical investigations. > They are totally defined. The key benefit is that algorithms that can be expressed in the x86 architecture that can be specified on ten pages could take hundreds of millions of pages for a TM. Just moving to tape head from memory location 0 to memory location 1,000,000 takes a printout five feet thick. -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | André G. Isaak <agisaak@gm.invalid> |
|---|---|
| Date | 2021-05-01 23:07 -0600 |
| Message-ID | <s6lc2g$gbd$1@dont-email.me> |
| In reply to | #32554 |
On 2021-05-01 22:55, olcott wrote: > On 5/1/2021 8:53 PM, Ben Bacarisse wrote: >> olcott <NoOne@NoWhere.com> writes: >> >>> On 5/1/2021 7:56 PM, Ben Bacarisse wrote: >>>> olcott <NoOne@NoWhere.com> writes: >>>> >>>>> On 5/1/2021 4:49 PM, Ben Bacarisse wrote: >>>>>> olcott <NoOne@NoWhere.com> writes: >>>>>> >>>>>>> There seems to be little agreement on the precise details of what is >>>>>>> and what is not a computation in computer science across respondents >>>>>>> here and textbook definitions. >>>>>> >>>>>> No. /You/ may me confused by slightly different definitions, but >>>>>> there >>>>>> is no substantive disagreement on this matter. >>>>>> >>>>>>> Since the input finite string can possibly be empty a Turing >>>>>>> machine M >>>>>>> that simply transitions from its start state to its final state >>>>>>> would >>>>>>> be a computable function. >>>>>> >>>>>> Category error. >>>>> >>>>> I had all three textbook definitions handy in the first link and tried >>>>> to correct my category error in the last paragraph. >>>> >>>> You /made/ the category error in the last paragraph. A TM can not be a >>>> computable function. The TM you describe computes the identity >>>> function. >>>> >>>>> The most significant difference of the textbook definitions is that >>>>> Sipser seems to think that a TM must erase its input. >>>> >>>> I knew you were confused, but I did not know you were this confused. >>> >>> Definition 5.12 >>> A function f: Σ* → Σ* is a computable function if some Turing machine >>> M, on every input w, halts with just f(w) on its tape. >>> >>> If only f(w) is on its tape that means that w is <not> on its tape. >>> The function of an input is <only> its output. >>> >>> So maybe I should have "interpreted" [just f(w) on its tape] to >>> mean Not[just f(w) on its tape] ??? >> >> No, your interpretation is correct. >> >> The quickest way to find out what I think you are confused by would be >> to ask me. Speculating on what I mean has a very low success rate for >> you. Had you asked, I'd have said you are confused in thinking Siper's >> definition is different in this regard. >> >> As it happens, Siper's is the odd one out, but for a totally different >> reason. >> >>>>> The textbooks seem to be pretty close. When respondents here talk >>>>> about disallowed side-effects they greatly diverge from the actual >>>>> theory of computation and digress into software engineering. >>>> >>>> They are trying to stop you playing silly games with your informal, >>>> hacked up, "model" of computation. It is you that have abandoned the >>>> theory and are grubbing about with x86 code and mysterious hidden C >>>> functions. >>>> >>>> With a proper model, the whole issue vanishes. TMs don't have >>>> side-effects >>> >>> I knew that this was impossible. Not everyone here knows that. >> >> That depends on "here". I see you have fished in the C and C++ ponds >> again and hooked someone who does not know the subject well. I don't >> think anyone you have been talking to regularly "here" (comp.theory) is >> in any doubt about it. >> >>>> and properly constructed programs (no functions), written >>>> in any formal notation of your choice, wouldn't have side-effects >>>> either. It is your examples that use your messed up informal model >>>> that >>>> need to be kept on the straight and narrow about side-effects. >>> >>> I never brought up the issue of side-effects. It has nothing to do >>> with the theory of computation. >> >> You brought the subject up by describing Halts in terms that can only be >> explained by cheating using side-effects. > > None of the theory of comutation texts say anything like this. There > cannot actually be anything like a cheating side effect. I dare you to > cite any theory of computation source that says anything about chreating > side effects. > > A TM does whatever a TM does as long as it transforms an input finite > string into a final state it is free to do anything else inbetween > without the possibility of cheating side effects because TMs are > incapable of cheating and any side-effects are part of the computation. But you're not actually working with TMs. You're working with C Code. Textbooks on the theory of computation aren't going to mention anything about side effects because actual Turing Machines *can't* have side effects. There's a reason why textbooks on computational theory don't frame things in terms of C or assembly but in terms of Turing Machines. You can create subroutines in C or assembly which *aren't* actual computations and which may have side effects, but it isn't possible to do this with Turing Machines. André >> Of course, you are still >> hiding the code, and by the time you publish anything, you may have >> found a way to remove the behaviour you have described to us. > > You have to accept the code before you see it on the basis of its > design. If you are incapable of doing that then you are unqualified to > evaluate it. > >>>>> My intention is to have this equally apply to TMs and x86 programs: >>>>> A [computation] is some sequence of mechanical steps that begins at a >>>>> start state (initial configuration) and ends in some specific final >>>>> state (final configuration) on some possibly empty input finite >>>>> string. >> >> Do you think that Turing machine states and machine configuration are >> the same thing? The use of clarifying (explanatory) parentheses hints >> at it. >> > > When use generically the whole state of a machine is the value of every > memory location. When applied to TMs is has a more specific meaning. > >>>> It is not true of TMs (unless you are changing how the term >>>> "computation" has been used for months in these threads), but it is not >>>> even wrong about x86 programs. >>> >>> What is the most correct, succinct way to say it? >> >> A computation is the sequence of configurations generated by the state >> transition function of a TM and an initial input string. This sequence >> is either finite or infinite. > > That sound pretty good now can be make it generic across every model of > computation? The initial state of an x86 machine is the value of each > memory location, the value of each register. The final state is the same > thing. > >> >> The most succinct way to expand on this (some of these are technical >> terms) would make use of a simpler definition of a Turing machine >> without any final states, but that would probably make you think I was >> mad. >> >> I would not try to say anything like this about x86 programs. They are >> not properly defined, not Turing complete and don't constitute a model >> of computation suitable for theoretical investigations. >> > > They are totally defined. The key benefit is that algorithms that can be > expressed in the x86 architecture that can be specified on ten pages > could take hundreds of millions of pages for a TM. Just moving to tape > head from memory location 0 to memory location 1,000,000 takes a > printout five feet thick. > > -- To email remove 'invalid' & replace 'gm' with well known Google mail service.
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2021-05-02 08:10 -0400 |
| Message-ID | <wEwjI.20800$7u1.2184@fx12.iad> |
| In reply to | #32554 |
On 5/2/21 12:55 AM, olcott wrote: > On 5/1/2021 8:53 PM, Ben Bacarisse wrote: >> olcott <NoOne@NoWhere.com> writes: >> >>> On 5/1/2021 7:56 PM, Ben Bacarisse wrote: >>>> olcott <NoOne@NoWhere.com> writes: >>>> >>>>> On 5/1/2021 4:49 PM, Ben Bacarisse wrote: >>>>>> olcott <NoOne@NoWhere.com> writes: >>>>>> >>>>>>> There seems to be little agreement on the precise details of what is >>>>>>> and what is not a computation in computer science across respondents >>>>>>> here and textbook definitions. >>>>>> >>>>>> No. /You/ may me confused by slightly different definitions, but >>>>>> there >>>>>> is no substantive disagreement on this matter. >>>>>> >>>>>>> Since the input finite string can possibly be empty a Turing >>>>>>> machine M >>>>>>> that simply transitions from its start state to its final state >>>>>>> would >>>>>>> be a computable function. >>>>>> >>>>>> Category error. >>>>> >>>>> I had all three textbook definitions handy in the first link and tried >>>>> to correct my category error in the last paragraph. >>>> >>>> You /made/ the category error in the last paragraph. A TM can not be a >>>> computable function. The TM you describe computes the identity >>>> function. >>>> >>>>> The most significant difference of the textbook definitions is that >>>>> Sipser seems to think that a TM must erase its input. >>>> >>>> I knew you were confused, but I did not know you were this confused. >>> >>> Definition 5.12 >>> A function f: Σ* → Σ* is a computable function if some Turing machine >>> M, on every input w, halts with just f(w) on its tape. >>> >>> If only f(w) is on its tape that means that w is <not> on its tape. >>> The function of an input is <only> its output. >>> >>> So maybe I should have "interpreted" [just f(w) on its tape] to >>> mean Not[just f(w) on its tape] ??? >> >> No, your interpretation is correct. >> >> The quickest way to find out what I think you are confused by would be >> to ask me. Speculating on what I mean has a very low success rate for >> you. Had you asked, I'd have said you are confused in thinking Siper's >> definition is different in this regard. >> >> As it happens, Siper's is the odd one out, but for a totally different >> reason. >> >>>>> The textbooks seem to be pretty close. When respondents here talk >>>>> about disallowed side-effects they greatly diverge from the actual >>>>> theory of computation and digress into software engineering. >>>> >>>> They are trying to stop you playing silly games with your informal, >>>> hacked up, "model" of computation. It is you that have abandoned the >>>> theory and are grubbing about with x86 code and mysterious hidden C >>>> functions. >>>> >>>> With a proper model, the whole issue vanishes. TMs don't have >>>> side-effects >>> >>> I knew that this was impossible. Not everyone here knows that. >> >> That depends on "here". I see you have fished in the C and C++ ponds >> again and hooked someone who does not know the subject well. I don't >> think anyone you have been talking to regularly "here" (comp.theory) is >> in any doubt about it. >> >>>> and properly constructed programs (no functions), written >>>> in any formal notation of your choice, wouldn't have side-effects >>>> either. It is your examples that use your messed up informal model >>>> that >>>> need to be kept on the straight and narrow about side-effects. >>> >>> I never brought up the issue of side-effects. It has nothing to do >>> with the theory of computation. >> >> You brought the subject up by describing Halts in terms that can only be >> explained by cheating using side-effects. > > None of the theory of comutation texts say anything like this. There > cannot actually be anything like a cheating side effect. I dare you to > cite any theory of computation source that says anything about chreating > side effects. > > A TM does whatever a TM does as long as it transforms an input finite > string into a final state it is free to do anything else inbetween > without the possibility of cheating side effects because TMs are > incapable of cheating and any side-effects are part of the computation. The key aspect is that Turing Machine, by their nature, can not 'cheat' in this way. Thus when talking about Turing Machines, you don't need to mention it. Only when when talking about non-Turing computation engines do you need to look at these facts, and if you are looking at code that IS the equivalent of a Turing Machine, then it won't do any of these things, it can't because then it wouldn't be the equivalent of a Turing Machine. It is only with code fragments that you don't KNOW are Turing Equivalents does the issue come up. If you do this sort of 'cheat', then your fragment ISN'T an equivalent of a Turing Machine, because it isn't a Computation. > >> Of course, you are still >> hiding the code, and by the time you publish anything, you may have >> found a way to remove the behaviour you have described to us. > > You have to accept the code before you see it on the basis of its > design. If you are incapable of doing that then you are unqualified to > evaluate it. What, you want someone to accept that something is correct before they get to inspect it, THAT is preposterous. Will you accept my arguement before I present it? Really would you? > >>>>> My intention is to have this equally apply to TMs and x86 programs: >>>>> A [computation] is some sequence of mechanical steps that begins at a >>>>> start state (initial configuration) and ends in some specific final >>>>> state (final configuration) on some possibly empty input finite >>>>> string. >> >> Do you think that Turing machine states and machine configuration are >> the same thing? The use of clarifying (explanatory) parentheses hints >> at it. >> > > When use generically the whole state of a machine is the value of every > memory location. When applied to TMs is has a more specific meaning. Yes, but then the machine no longer has its defined input, and thus Halts doesn't qualify as a Halt Decider, because BY DEFINITION, a Halt Decider decides on EXACTLY a description of the Turing Machine and its input. To properly do its job, it can't need any other inputs, and if it does, then it can't be doing its job properly. Since it seems that you Halt Decider 'Halts' wants to have more informatation than allowed, it isn't a Halt Decider. > >>>> It is not true of TMs (unless you are changing how the term >>>> "computation" has been used for months in these threads), but it is not >>>> even wrong about x86 programs. >>> >>> What is the most correct, succinct way to say it? >> >> A computation is the sequence of configurations generated by the state >> transition function of a TM and an initial input string. This sequence >> is either finite or infinite. > > That sound pretty good now can be make it generic across every model of > computation? The initial state of an x86 machine is the value of each > memory location, the value of each register. The final state is the same > thing. That is the flaw in yout goal. Turing Machines work well for the Theory of Computation, because all Turing Machines work precisely as a Computation with a limited predefined input and output. Your generic machine, has a LOT of memory that gets in the way of this. If we include it as part of the input, then we have a LOT of information defined as being part of the computation that we don't want. If we don't include it as the input, then the code might 'cheat' and not BE a computation. If I want to ask what 1 + 2 is, the only inputs should be 1 and 2, not the OS that is loaded into the machine. Yes, you can 'define' the code to be a computation, but you can't make it be THE computation you want it to do. > >> >> The most succinct way to expand on this (some of these are technical >> terms) would make use of a simpler definition of a Turing machine >> without any final states, but that would probably make you think I was >> mad. >> >> I would not try to say anything like this about x86 programs. They are >> not properly defined, not Turing complete and don't constitute a model >> of computation suitable for theoretical investigations. >> > > They are totally defined. The key benefit is that algorithms that can be > expressed in the x86 architecture that can be specified on ten pages > could take hundreds of millions of pages for a TM. Just moving to tape > head from memory location 0 to memory location 1,000,000 takes a > printout five feet thick. > >
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-05-02 20:29 +0100 |
| Message-ID | <878s4x7x44.fsf@bsb.me.uk> |
| In reply to | #32554 |
olcott <NoOne@NoWhere.com> writes: > On 5/1/2021 8:53 PM, Ben Bacarisse wrote: >> olcott <NoOne@NoWhere.com> writes: >> >>> On 5/1/2021 7:56 PM, Ben Bacarisse wrote: >>>> olcott <NoOne@NoWhere.com> writes: >>>> >>>>> On 5/1/2021 4:49 PM, Ben Bacarisse wrote: >>>>>> olcott <NoOne@NoWhere.com> writes: >>>>>> >>>>>>> There seems to be little agreement on the precise details of what is >>>>>>> and what is not a computation in computer science across respondents >>>>>>> here and textbook definitions. >>>>>> >>>>>> No. /You/ may me confused by slightly different definitions, but there >>>>>> is no substantive disagreement on this matter. >>>>>> >>>>>>> Since the input finite string can possibly be empty a Turing machine M >>>>>>> that simply transitions from its start state to its final state would >>>>>>> be a computable function. >>>>>> >>>>>> Category error. >>>>> >>>>> I had all three textbook definitions handy in the first link and tried >>>>> to correct my category error in the last paragraph. >>>> >>>> You /made/ the category error in the last paragraph. A TM can not be a >>>> computable function. The TM you describe computes the identity function. >>>> >>>>> The most significant difference of the textbook definitions is that >>>>> Sipser seems to think that a TM must erase its input. >>>> >>>> I knew you were confused, but I did not know you were this confused. >>> >>> Definition 5.12 >>> A function f: Σ* → Σ* is a computable function if some Turing machine >>> M, on every input w, halts with just f(w) on its tape. >>> >>> If only f(w) is on its tape that means that w is <not> on its tape. >>> The function of an input is <only> its output. >>> >>> So maybe I should have "interpreted" [just f(w) on its tape] to >>> mean Not[just f(w) on its tape] ??? >> >> No, your interpretation is correct. >> >> The quickest way to find out what I think you are confused by would be >> to ask me. Speculating on what I mean has a very low success rate for >> you. Had you asked, I'd have said you are confused in thinking Siper's >> definition is different in this regard. >> >> As it happens, Siper's is the odd one out, but for a totally different >> reason. >> >>>>> The textbooks seem to be pretty close. When respondents here talk >>>>> about disallowed side-effects they greatly diverge from the actual >>>>> theory of computation and digress into software engineering. >>>> >>>> They are trying to stop you playing silly games with your informal, >>>> hacked up, "model" of computation. It is you that have abandoned the >>>> theory and are grubbing about with x86 code and mysterious hidden C >>>> functions. >>>> >>>> With a proper model, the whole issue vanishes. TMs don't have >>>> side-effects >>> >>> I knew that this was impossible. Not everyone here knows that. >> >> That depends on "here". I see you have fished in the C and C++ ponds >> again and hooked someone who does not know the subject well. I don't >> think anyone you have been talking to regularly "here" (comp.theory) is >> in any doubt about it. >> >>>> and properly constructed programs (no functions), written >>>> in any formal notation of your choice, wouldn't have side-effects >>>> either. It is your examples that use your messed up informal model that >>>> need to be kept on the straight and narrow about side-effects. >>> >>> I never brought up the issue of side-effects. It has nothing to do >>> with the theory of computation. >> >> You brought the subject up by describing Halts in terms that can only be >> explained by cheating using side-effects. > > None of the theory of comutation texts say anything like this. None of them deal with nonsense like yours. > There cannot actually be anything like a cheating side effect. I dare > you to cite any theory of computation source that says anything about > chreating side effects. You are not doing theoretical computer science. You are a programmer writing bad C code and withholding it to hide the way it cheats. There can be no CS reference to the idea of a cheating side effect, just as there can be no CS reference to a cheating lover. > A TM does whatever a TM does... Yes, and they are simple, clear and unambiguous. What a shame it was a lie when you said your had two fully encoded, actual Turing machines, exactly and precisely as in Linz. Imagine! This could have been over in Dec 2018. Because they are clear, you quickly realised that you need a great deal of hidden code in which to hide whatever mistake you had originally made, but it won't work. You have tipped your hand. You declare false to be the correct answer for an infinite computation based on what another, different, computation. Or, as you like to try to spin it, what the original computation would do if it were different. >> Of course, you are still >> hiding the code, and by the time you publish anything, you may have >> found a way to remove the behaviour you have described to us. > > You have to accept the code before you see it on the basis of its > design. If you are incapable of doing that then you are unqualified to > evaluate it. Why do you think I have to accept that? I happy to note that this is today's excuse, but you can't compel me to accept anything. But I love the phrase "you have to accept the code before you see it". It's just priceless! >>>>> My intention is to have this equally apply to TMs and x86 programs: >>>>> A [computation] is some sequence of mechanical steps that begins at a >>>>> start state (initial configuration) and ends in some specific final >>>>> state (final configuration) on some possibly empty input finite >>>>> string. >> >> Do you think that Turing machine states and machine configuration are >> the same thing? The use of clarifying (explanatory) parentheses hints >> at it. > > When use generically the whole state of a machine is the value of > every memory location. When applied to TMs is has a more specific > meaning. Which you don't know, do you? Look it up and then copy-and-paste the definition so we will all think you knew it from the start. Not. >>>> It is not true of TMs (unless you are changing how the term >>>> "computation" has been used for months in these threads), but it is not >>>> even wrong about x86 programs. >>> >>> What is the most correct, succinct way to say it? >> >> A computation is the sequence of configurations generated by the state >> transition function of a TM and an initial input string. This sequence >> is either finite or infinite. > > That sound pretty good Thank you. > now can be make it generic across every model of computation? No. > The initial state of an x86 machine is the value of each memory > location, the value of each register. The final state is the same > thing. That's not a model of computation. It's you using what you know and trying to pretend that it's a model of computation. >> The most succinct way to expand on this (some of these are technical >> terms) would make use of a simpler definition of a Turing machine >> without any final states, but that would probably make you think I was >> mad. >> >> I would not try to say anything like this about x86 programs. They are >> not properly defined, not Turing complete and don't constitute a model >> of computation suitable for theoretical investigations. > > They are totally defined. Nope. How many bugs are there in any particular x86 architecture? How many bugs are there in any of the specifications? Have you ever defined what instructions you permit and which you don't? What mode or modes? The list goes on... > The key benefit is that algorithms that can be expressed in the x86 > architecture that can be specified on ten pages could take hundreds of > millions of pages for a TM. There are even higher-level models that would suit much better. But they are outside your comfort zone, so crappy x86 code it must be. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | olcott <NoOne@NoWhere.com> |
|---|---|
| Date | 2021-05-02 14:34 -0500 |
| Message-ID | <zMqdncUcr8QEYxP9nZ2dnUU7-fXNnZ2d@giganews.com> |
| In reply to | #32585 |
On 5/2/2021 2:29 PM, Ben Bacarisse wrote: > olcott <NoOne@NoWhere.com> writes: > >> On 5/1/2021 8:53 PM, Ben Bacarisse wrote: >>> olcott <NoOne@NoWhere.com> writes: >>> >>>> On 5/1/2021 7:56 PM, Ben Bacarisse wrote: >>>>> olcott <NoOne@NoWhere.com> writes: >>>>> >>>>>> On 5/1/2021 4:49 PM, Ben Bacarisse wrote: >>>>>>> olcott <NoOne@NoWhere.com> writes: >>>>>>> >>>>>>>> There seems to be little agreement on the precise details of what is >>>>>>>> and what is not a computation in computer science across respondents >>>>>>>> here and textbook definitions. >>>>>>> >>>>>>> No. /You/ may me confused by slightly different definitions, but there >>>>>>> is no substantive disagreement on this matter. >>>>>>> >>>>>>>> Since the input finite string can possibly be empty a Turing machine M >>>>>>>> that simply transitions from its start state to its final state would >>>>>>>> be a computable function. >>>>>>> >>>>>>> Category error. >>>>>> >>>>>> I had all three textbook definitions handy in the first link and tried >>>>>> to correct my category error in the last paragraph. >>>>> >>>>> You /made/ the category error in the last paragraph. A TM can not be a >>>>> computable function. The TM you describe computes the identity function. >>>>> >>>>>> The most significant difference of the textbook definitions is that >>>>>> Sipser seems to think that a TM must erase its input. >>>>> >>>>> I knew you were confused, but I did not know you were this confused. >>>> >>>> Definition 5.12 >>>> A function f: Σ* → Σ* is a computable function if some Turing machine >>>> M, on every input w, halts with just f(w) on its tape. >>>> >>>> If only f(w) is on its tape that means that w is <not> on its tape. >>>> The function of an input is <only> its output. >>>> >>>> So maybe I should have "interpreted" [just f(w) on its tape] to >>>> mean Not[just f(w) on its tape] ??? >>> >>> No, your interpretation is correct. >>> >>> The quickest way to find out what I think you are confused by would be >>> to ask me. Speculating on what I mean has a very low success rate for >>> you. Had you asked, I'd have said you are confused in thinking Siper's >>> definition is different in this regard. >>> >>> As it happens, Siper's is the odd one out, but for a totally different >>> reason. >>> >>>>>> The textbooks seem to be pretty close. When respondents here talk >>>>>> about disallowed side-effects they greatly diverge from the actual >>>>>> theory of computation and digress into software engineering. >>>>> >>>>> They are trying to stop you playing silly games with your informal, >>>>> hacked up, "model" of computation. It is you that have abandoned the >>>>> theory and are grubbing about with x86 code and mysterious hidden C >>>>> functions. >>>>> >>>>> With a proper model, the whole issue vanishes. TMs don't have >>>>> side-effects >>>> >>>> I knew that this was impossible. Not everyone here knows that. >>> >>> That depends on "here". I see you have fished in the C and C++ ponds >>> again and hooked someone who does not know the subject well. I don't >>> think anyone you have been talking to regularly "here" (comp.theory) is >>> in any doubt about it. >>> >>>>> and properly constructed programs (no functions), written >>>>> in any formal notation of your choice, wouldn't have side-effects >>>>> either. It is your examples that use your messed up informal model that >>>>> need to be kept on the straight and narrow about side-effects. >>>> >>>> I never brought up the issue of side-effects. It has nothing to do >>>> with the theory of computation. >>> >>> You brought the subject up by describing Halts in terms that can only be >>> explained by cheating using side-effects. >> >> None of the theory of comutation texts say anything like this. > > None of them deal with nonsense like yours. > >> There cannot actually be anything like a cheating side effect. I dare >> you to cite any theory of computation source that says anything about >> chreating side effects. > > You are not doing theoretical computer science. You are a programmer > writing bad C code and withholding it to hide the way it cheats. There > can be no CS reference to the idea of a cheating side effect, Because there is no such thing as any side-effect what-so-ever in any aspect of the theory of computation. As always I stop reading at the first big mistake. > just as > there can be no CS reference to a cheating lover. > >> A TM does whatever a TM does... > > Yes, and they are simple, clear and unambiguous. What a shame it was a > lie when you said your had two fully encoded, actual Turing machines, > exactly and precisely as in Linz. Imagine! This could have been over > in Dec 2018. > > Because they are clear, you quickly realised that you need a great deal > of hidden code in which to hide whatever mistake you had originally > made, but it won't work. You have tipped your hand. You declare false > to be the correct answer for an infinite computation based on what > another, different, computation. Or, as you like to try to spin it, > what the original computation would do if it were different. > >>> Of course, you are still >>> hiding the code, and by the time you publish anything, you may have >>> found a way to remove the behaviour you have described to us. >> >> You have to accept the code before you see it on the basis of its >> design. If you are incapable of doing that then you are unqualified to >> evaluate it. > > Why do you think I have to accept that? I happy to note that this is > today's excuse, but you can't compel me to accept anything. > > But I love the phrase "you have to accept the code before you see it". > It's just priceless! > >>>>>> My intention is to have this equally apply to TMs and x86 programs: >>>>>> A [computation] is some sequence of mechanical steps that begins at a >>>>>> start state (initial configuration) and ends in some specific final >>>>>> state (final configuration) on some possibly empty input finite >>>>>> string. >>> >>> Do you think that Turing machine states and machine configuration are >>> the same thing? The use of clarifying (explanatory) parentheses hints >>> at it. >> >> When use generically the whole state of a machine is the value of >> every memory location. When applied to TMs is has a more specific >> meaning. > > Which you don't know, do you? Look it up and then copy-and-paste the > definition so we will all think you knew it from the start. Not. > >>>>> It is not true of TMs (unless you are changing how the term >>>>> "computation" has been used for months in these threads), but it is not >>>>> even wrong about x86 programs. >>>> >>>> What is the most correct, succinct way to say it? >>> >>> A computation is the sequence of configurations generated by the state >>> transition function of a TM and an initial input string. This sequence >>> is either finite or infinite. >> >> That sound pretty good > > Thank you. > >> now can be make it generic across every model of computation? > > No. > >> The initial state of an x86 machine is the value of each memory >> location, the value of each register. The final state is the same >> thing. > > That's not a model of computation. It's you using what you know and > trying to pretend that it's a model of computation. > >>> The most succinct way to expand on this (some of these are technical >>> terms) would make use of a simpler definition of a Turing machine >>> without any final states, but that would probably make you think I was >>> mad. >>> >>> I would not try to say anything like this about x86 programs. They are >>> not properly defined, not Turing complete and don't constitute a model >>> of computation suitable for theoretical investigations. >> >> They are totally defined. > > Nope. How many bugs are there in any particular x86 architecture? How > many bugs are there in any of the specifications? Have you ever defined > what instructions you permit and which you don't? What mode or modes? > The list goes on... > >> The key benefit is that algorithms that can be expressed in the x86 >> architecture that can be specified on ten pages could take hundreds of >> millions of pages for a TM. > > There are even higher-level models that would suit much better. But > they are outside your comfort zone, so crappy x86 code it must be. > -- Copyright 2021 Pete Olcott "Great spirits have always encountered violent opposition from mediocre minds." Einstein
[toc] | [prev] | [next] | [standalone]
| From | Richard Damon <Richard@Damon-Family.org> |
|---|---|
| Date | 2021-05-02 15:48 -0400 |
| Message-ID | <%lDjI.330625$DJ2.128360@fx42.iad> |
| In reply to | #32587 |
On 5/2/21 3:34 PM, olcott wrote: > On 5/2/2021 2:29 PM, Ben Bacarisse wrote: >> >> You are not doing theoretical computer science. You are a programmer >> writing bad C code and withholding it to hide the way it cheats. There >> can be no CS reference to the idea of a cheating side effect, > > Because there is no such thing as any side-effect what-so-ever in any > aspect of the theory of computation. As always I stop reading at the > first big mistake. > Because the Theory of Computation you refer to there works with machines that can not have side effects, so doesn't need to mention them. If you look at the parts that talk about 'Equivalent Machines', that DOES talk about side-effects, and how there use makes it so that there isn't an equivalent in the simple sense.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2021-05-02 21:46 +0100 |
| Message-ID | <87r1io7tk1.fsf@bsb.me.uk> |
| In reply to | #32587 |
olcott <NoOne@NoWhere.com> writes: > On 5/2/2021 2:29 PM, Ben Bacarisse wrote: >> olcott <NoOne@NoWhere.com> writes: >> >>> On 5/1/2021 8:53 PM, Ben Bacarisse wrote: >>>> You brought the subject up by describing Halts in terms that can only be >>>> explained by cheating using side-effects. >>> >>> None of the theory of comutation texts say anything like this. >> >> None of them deal with nonsense like yours. >> >>> There cannot actually be anything like a cheating side effect. I dare >>> you to cite any theory of computation source that says anything about >>> chreating side effects. >> >> You are not doing theoretical computer science. You are a programmer >> writing bad C code and withholding it to hide the way it cheats. There >> can be no CS reference to the idea of a cheating side effect, > > Because there is no such thing as any side-effect what-so-ever in any > aspect of the theory of computation. As always I stop reading at the > first big mistake. What a shame you don't stop writing at the first big mistake. >> just as >> there can be no CS reference to a cheating lover. -- Ben.
[toc] | [prev] | [standalone]
Page 5 of 5 — ← Prev page 1 2 3 4 [5]
Back to top | Article view | comp.theory
csiph-web