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


Groups > comp.theory > #32496 > unrolled thread

Mutual agreement on the definition of a [computation] in computer science

Started byolcott <NoOne@NoWhere.com>
First post2021-05-01 11:30 -0500
Last post2021-05-02 21:46 +0100
Articles 12 on this page of 92 — 7 participants

Back to article view | Back to comp.theory


Contents

  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]


#32532

Fromolcott <NoOne@NoWhere.com>
Date2021-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]


#32537

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-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]


#32542

Fromolcott <NoOne@NoWhere.com>
Date2021-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]


#32547

FromRichard Damon <Richard@Damon-Family.org>
Date2021-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]


#32548

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-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]


#32554

Fromolcott <NoOne@NoWhere.com>
Date2021-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]


#32556

FromAndré G. Isaak <agisaak@gm.invalid>
Date2021-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]


#32560

FromRichard Damon <Richard@Damon-Family.org>
Date2021-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]


#32585

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-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]


#32587

Fromolcott <NoOne@NoWhere.com>
Date2021-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]


#32589

FromRichard Damon <Richard@Damon-Family.org>
Date2021-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]


#32593

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-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