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


Groups > comp.theory > #32506

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

Subject Re: Mutual agreement on the definition of a [computation] in computer science
Newsgroups comp.theory
References <sKudna-1asC9HxD9nZ2dnUU7-KnNnZ2d@giganews.com> <QZydnSMXcJArHhD9nZ2dnUU7-bOdnZ2d@giganews.com>
From Richard Damon <Richard@Damon-Family.org>
Message-ID <_ohjI.73721$sd3.27264@fx02.iad> (permalink)
Organization Forte - www.forteinc.com
Date 2021-05-01 14:49 -0400

Show all headers | View raw


On 5/1/21 12:37 PM, olcott wrote:
> On 5/1/2021 11:30 AM, olcott wrote:
>> 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.
>>
>> I will provide and analyze the textbook definitions of: {Linz, Sipser
>> and Kozen} for "computable function".
>>
>> A function f with domain f is said to be Turing-computable of just
>> computable if there exists some Turing machine M = (Q, Σ, Γ, δ, q0, □, F)
>>
>> such that q0w ⊢* Mqₘf(w), qₘ ∈ F, for all w ∈ D
>>
>> Paraphrase: Turing machine M begins in its start state and after
>> making an arbitrary number of moves on input w in domain D halts in a
>> final state of its set of final states of M.
>>
>> Linz, Peter 1990. An Introduction to Formal Languages and Automata.
>> Lexington/Toronto: D. C. Heath and Company. (243)
>>
>> Computable Functions
>> A Turing machine computes a function by starting with the input to the
>> function on the tape and halting with the output of the function on
>> the tape.
>>
>> 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.
>>
>> Paraphrase: Turing machine M transforms input finite string w into
>> output finite string M(w). This regular expression Σ* indicates zero
>> or more elements of Σ (the input alphabet).
>>
>> Sipser, Michael 1997. Introduction to the Theory of Computation.
>> Boston: PWS Publishing Company (190)
>>
>> A partial function σ: Σ* → Σ* is said to be a computable function if
>> σ(x) = M(x) for some Turing machine M.
>>
>> Kozen, Dexter 1997. Automata and Computability. New York:
>> Springer-Verlag. (347).
>>
>> When we combine all the definitions together we can simplify Linz and
>> instead of saying that w ∈ D, we say that w is a (possibly empty)
>> finite string of the input alphabet.
>>
>> All of the definitions require M to halt. Linz requires M to halt in a
>> final state of the final states of M. Kozen requires that an input
>> finite string derives an output finite string. Sipser require the same
>> a Kozen yet the input finite string must be also erased.
>>
>> If we unify these definitions we might say that a [computable
>> function] is some Turing machine M that makes an arbitrary number of
>> moves on a some (possibly empty) finite string w ∈ Σ* of its input
>> alphabet and ends up in a final state of its set of final states.
>>
>> Optionally there may be some finite string x ∈ Σ* of its input
>> alphabet on it tape. I will ignore the apparent Sipser requirement to
>> erase the input string.
>>
>> 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.
>>
> 
> A [computable function] is some Turing machine M that makes an arbitrary
> number of moves from its start state on a some (possibly empty) finite
> string w ∈ Σ* of its input alphabet and ends up in a final state of its
> set of final states.
> 
> Optionally there may be some finite string x ∈ Σ* output left on its
> tape.  Because the input string can be empty and the output string is
> optional the definition of [computable function] would define a
> [computation] as any Turing machine that halts.
> 

One consequence of this definition that you seem to be missing is that
for a given input a given machine will ALWAYS give the same output
(final state + contents of tape). This is a direct consequence of how
Turing Machines work, but if you want to define the Computation /
Computable Function independent of a Turing Machine, this becomes part
of its requirements.

Note, you don't really need to treat the 'Empty Tape' as a special case,
as it is just a tape with zero symbols on it. The Computation might
define that you ignore the output tape, and just treat the state it
halted in, or even just that it halted as the 'output'.

Some of the variations depends a bit on exactly what branch or use of
Computation theory you are using. I think Computable Function always
implies that the Computation is finite (and thus Halt-Deciding is asking
does the Turing Machine with that input define a Computable Function or
not). Computation sometimes is just a synonym for this, or sometimes
includes the case where the Turing Machine never halts, being merely the
effect of combining a Turing Machine with an input Tape.

One other comment, the Computable Function isn't the Turing Machine
itself in the normal definitions, but the mapping of input to output,
the Turing Machine is just the implementation of it.

More specifically, Computatable Function refers to the mapping,
Computation deals with how that is done, being the combination of an
Algorithm (which the Turing Machine implements) and an input data (the
Tape of the Turing Machine). An Algorithm being a finite listing of
'mechanical' steps to perform to do the Computation to get the
Computable Function.

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