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


Groups > comp.theory > #32548

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

From Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups comp.theory
Subject Re: Mutual agreement on the definition of a [computation] in computer science
Date 2021-05-02 02:53 +0100
Organization A noiseless patient Spider
Message-ID <87czu9aoke.fsf@bsb.me.uk> (permalink)
References <sKudna-1asC9HxD9nZ2dnUU7-KnNnZ2d@giganews.com> <87k0oiazun.fsf@bsb.me.uk> <QsednVs36qATeBD9nZ2dnUU7-XXNnZ2d@giganews.com> <87o8du9cnv.fsf@bsb.me.uk> <yvednXcPGP40YxD9nZ2dnUU7-aPNnZ2d@giganews.com>

Show all headers | View raw


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.

Back to comp.theory | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread


Thread

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

csiph-web