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 20 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 1 of 5  [1] 2 3 4 5  Next page →


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

Fromolcott <NoOne@NoWhere.com>
Date2021-05-01 11:30 -0500
SubjectMutual agreement on the definition of a [computation] in computer science
Message-ID<sKudna-1asC9HxD9nZ2dnUU7-KnNnZ2d@giganews.com>
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.

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [next] | [standalone]


#32497

Fromolcott <NoOne@NoWhere.com>
Date2021-05-01 11:37 -0500
Message-ID<QZydnSMXcJArHhD9nZ2dnUU7-bOdnZ2d@giganews.com>
In reply to#32496
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.



-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#32500

Fromolcott <NoOne@NoWhere.com>
Date2021-05-01 12:40 -0500
Message-ID<AYGdnY-0pOLoDxD9nZ2dnUU7-IXNnZ2d@giganews.com>
In reply to#32497
On 5/1/2021 11:37 AM, 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.


To make [computable function] generic to all models of computation:
A [computable function] 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]


#32507

FromRichard Damon <Richard@Damon-Family.org>
Date2021-05-01 14:55 -0400
Message-ID<EuhjI.165643$ST2.137973@fx47.iad>
In reply to#32500
On 5/1/21 1:40 PM, olcott wrote:
> On 5/1/2021 11:37 AM, 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.
> 
> 
> To make [computable function] generic to all models of computation:
> A [computable function] 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.
> 
> 
As I mentioned in my other reply, once you leave the domain of Turing
Machines, the requirement of a given input always giving the same output
becomes an important restriction, and a necessity for the operation to
be able to have a Turing Machine equivalent.

More specifically, the definition of the Computable Function needs to
include ALL of the data and algorithmic steps that go into the
Computation behind that function. The operation can't depend on data
that is acquired outside the formally defined inputs to it, and can't
use mechanical steps that don't belong to it.

[toc] | [prev] | [next] | [standalone]


#32511

Fromolcott <NoOne@NoWhere.com>
Date2021-05-01 14:09 -0500
Message-ID<T6GdncKpA52nOhD9nZ2dnUU7-dPNnZ2d@giganews.com>
In reply to#32507
On 5/1/2021 1:55 PM, Richard Damon wrote:
> On 5/1/21 1:40 PM, olcott wrote:
>> On 5/1/2021 11:37 AM, 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.
>>
>>
>> To make [computable function] generic to all models of computation:
>> A [computable function] 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.
>>
>>
> As I mentioned in my other reply, once you leave the domain of Turing
> Machines, the requirement of a given input always giving the same output
> becomes an important restriction, and a necessity for the operation to
> be able to have a Turing Machine equivalent.
> 

In the case of the mapping from Halts(H_Hat, H_Hat) to a final state 
indicating "No" (not halting) it can perform any mechanical steps in any 
way as long as the mapping from the input to the final state always 
produces the same result.

The part that you can never seem to understand is that between the start 
state and the final state this machine is free to do anything that 
machines can possibly do. You have never seemed to get this part.

> More specifically, the definition of the Computable Function needs to
> include ALL of the data and algorithmic steps that go into the
> Computation behind that function. The operation can't depend on data
> that is acquired outside the formally defined inputs to it, and can't
> use mechanical steps that don't belong to it.
> 


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#32516

FromMr Flibble <flibble@i42.REMOVETHISBIT.co.uk>
Date2021-05-01 22:42 +0100
Message-ID<KWjjI.241617$Qjyf.180556@fx14.ams4>
In reply to#32511
On 01/05/2021 20:09, olcott wrote:
> On 5/1/2021 1:55 PM, Richard Damon wrote:
>> On 5/1/21 1:40 PM, olcott wrote:
>>> On 5/1/2021 11:37 AM, 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.
>>>
>>>
>>> To make [computable function] generic to all models of computation:
>>> A [computable function] 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.
>>>
>>>
>> As I mentioned in my other reply, once you leave the domain of Turing
>> Machines, the requirement of a given input always giving the same output
>> becomes an important restriction, and a necessity for the operation to
>> be able to have a Turing Machine equivalent.
>>
> 
> In the case of the mapping from Halts(H_Hat, H_Hat) to a final state indicating 
> "No" (not halting) it can perform any mechanical steps in any way as long as the 
> mapping from the input to the final state always produces the same result.
> 
> The part that you can never seem to understand is that between the start state 
> and the final state this machine is free to do anything that machines can 
> possibly do. You have never seemed to get this part.

Nonsense. Any side effects over and above those allowed for a TM means we are no 
longer dealing with a TM.

/Flibble

-- 
😎

[toc] | [prev] | [next] | [standalone]


#32522

Fromolcott <NoOne@NoWhere.com>
Date2021-05-01 17:32 -0500
Message-ID<eMOdnd0RlLhDSxD9nZ2dnUU7-LWdnZ2d@giganews.com>
In reply to#32516
On 5/1/2021 4:42 PM, Mr Flibble wrote:
> On 01/05/2021 20:09, olcott wrote:
>> On 5/1/2021 1:55 PM, Richard Damon wrote:
>>> On 5/1/21 1:40 PM, olcott wrote:
>>>> On 5/1/2021 11:37 AM, 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.
>>>>
>>>>
>>>> To make [computable function] generic to all models of computation:
>>>> A [computable function] 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.
>>>>
>>>>
>>> As I mentioned in my other reply, once you leave the domain of Turing
>>> Machines, the requirement of a given input always giving the same output
>>> becomes an important restriction, and a necessity for the operation to
>>> be able to have a Turing Machine equivalent.
>>>
>>
>> In the case of the mapping from Halts(H_Hat, H_Hat) to a final state 
>> indicating "No" (not halting) it can perform any mechanical steps in 
>> any way as long as the mapping from the input to the final state 
>> always produces the same result.
>>
>> The part that you can never seem to understand is that between the 
>> start state and the final state this machine is free to do anything 
>> that machines can possibly do. You have never seemed to get this part.
> 
> Nonsense. Any side effects over and above those allowed for a TM means 
> we are no longer dealing with a TM.
> 
> /Flibble
> 

To the best of my knowledge "side effect" is a software engineering term 
that has no application what-so-ever to the theory of computation. So 
far no one has been able to cite any source saying otherwise. On this 
basis I am tentatively concluding that you are simply wrong.

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#32524

FromRichard Damon <Richard@Damon-Family.org>
Date2021-05-01 18:43 -0400
Message-ID<nQkjI.31369$IC5.28366@fx24.iad>
In reply to#32522
On 5/1/21 6:32 PM, olcott wrote:
> On 5/1/2021 4:42 PM, Mr Flibble wrote:
>> On 01/05/2021 20:09, olcott wrote:
>>> On 5/1/2021 1:55 PM, Richard Damon wrote:
>>>> On 5/1/21 1:40 PM, olcott wrote:
>>>>> On 5/1/2021 11:37 AM, 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.
>>>>>
>>>>>
>>>>> To make [computable function] generic to all models of computation:
>>>>> A [computable function] 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.
>>>>>
>>>>>
>>>> As I mentioned in my other reply, once you leave the domain of Turing
>>>> Machines, the requirement of a given input always giving the same
>>>> output
>>>> becomes an important restriction, and a necessity for the operation to
>>>> be able to have a Turing Machine equivalent.
>>>>
>>>
>>> In the case of the mapping from Halts(H_Hat, H_Hat) to a final state
>>> indicating "No" (not halting) it can perform any mechanical steps in
>>> any way as long as the mapping from the input to the final state
>>> always produces the same result.
>>>
>>> The part that you can never seem to understand is that between the
>>> start state and the final state this machine is free to do anything
>>> that machines can possibly do. You have never seemed to get this part.
>>
>> Nonsense. Any side effects over and above those allowed for a TM means
>> we are no longer dealing with a TM.
>>
>> /Flibble
>>
> 
> To the best of my knowledge "side effect" is a software engineering term
> that has no application what-so-ever to the theory of computation. So
> far no one has been able to cite any source saying otherwise. On this
> basis I am tentatively concluding that you are simply wrong.
> 

The key is that you can't be using a 'side effect' (like a static
variable) to get around the requirements for being a Computation,
getting information from a source that isn't part of your inputs.

It also means you can't change things that you aren't allowed to change,
like the stuff that 'called' you.

[toc] | [prev] | [next] | [standalone]


#32530

Fromolcott <NoOne@NoWhere.com>
Date2021-05-01 18:16 -0500
Message-ID<LO-dnfAz5K6yfBD9nZ2dnUU7-ROdnZ2d@giganews.com>
In reply to#32524
On 5/1/2021 5:43 PM, Richard Damon wrote:
> On 5/1/21 6:32 PM, olcott wrote:
>> On 5/1/2021 4:42 PM, Mr Flibble wrote:
>>> On 01/05/2021 20:09, olcott wrote:
>>>> On 5/1/2021 1:55 PM, Richard Damon wrote:
>>>>> On 5/1/21 1:40 PM, olcott wrote:
>>>>>> On 5/1/2021 11:37 AM, 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.
>>>>>>
>>>>>>
>>>>>> To make [computable function] generic to all models of computation:
>>>>>> A [computable function] 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.
>>>>>>
>>>>>>
>>>>> As I mentioned in my other reply, once you leave the domain of Turing
>>>>> Machines, the requirement of a given input always giving the same
>>>>> output
>>>>> becomes an important restriction, and a necessity for the operation to
>>>>> be able to have a Turing Machine equivalent.
>>>>>
>>>>
>>>> In the case of the mapping from Halts(H_Hat, H_Hat) to a final state
>>>> indicating "No" (not halting) it can perform any mechanical steps in
>>>> any way as long as the mapping from the input to the final state
>>>> always produces the same result.
>>>>
>>>> The part that you can never seem to understand is that between the
>>>> start state and the final state this machine is free to do anything
>>>> that machines can possibly do. You have never seemed to get this part.
>>>
>>> Nonsense. Any side effects over and above those allowed for a TM means
>>> we are no longer dealing with a TM.
>>>
>>> /Flibble
>>>
>>
>> To the best of my knowledge "side effect" is a software engineering term
>> that has no application what-so-ever to the theory of computation. So
>> far no one has been able to cite any source saying otherwise. On this
>> basis I am tentatively concluding that you are simply wrong.
>>
> 
> The key is that you can't be using a 'side effect' (like a static
> variable) to get around the requirements for being a Computation,
> getting information from a source that isn't part of your inputs.
> 
> It also means you can't change things that you aren't allowed to change,
> like the stuff that 'called' you.
> 

A TM does whatever a TM does there is no sort of sanctioned behavior or 
unsanctioned behavior.

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#32541

FromRichard Damon <Richard@Damon-Family.org>
Date2021-05-01 21:20 -0400
Message-ID<18njI.79273$Sx7.25892@fx18.iad>
In reply to#32530
On 5/1/21 7:16 PM, olcott wrote:
> On 5/1/2021 5:43 PM, Richard Damon wrote:
>> On 5/1/21 6:32 PM, olcott wrote:
>>> On 5/1/2021 4:42 PM, Mr Flibble wrote:
>>>> On 01/05/2021 20:09, olcott wrote:
>>>>> On 5/1/2021 1:55 PM, Richard Damon wrote:
>>>>>> On 5/1/21 1:40 PM, olcott wrote:
>>>>>>> On 5/1/2021 11:37 AM, 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.
>>>>>>>
>>>>>>>
>>>>>>> To make [computable function] generic to all models of computation:
>>>>>>> A [computable function] 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.
>>>>>>>
>>>>>>>
>>>>>> As I mentioned in my other reply, once you leave the domain of Turing
>>>>>> Machines, the requirement of a given input always giving the same
>>>>>> output
>>>>>> becomes an important restriction, and a necessity for the
>>>>>> operation to
>>>>>> be able to have a Turing Machine equivalent.
>>>>>>
>>>>>
>>>>> In the case of the mapping from Halts(H_Hat, H_Hat) to a final state
>>>>> indicating "No" (not halting) it can perform any mechanical steps in
>>>>> any way as long as the mapping from the input to the final state
>>>>> always produces the same result.
>>>>>
>>>>> The part that you can never seem to understand is that between the
>>>>> start state and the final state this machine is free to do anything
>>>>> that machines can possibly do. You have never seemed to get this part.
>>>>
>>>> Nonsense. Any side effects over and above those allowed for a TM means
>>>> we are no longer dealing with a TM.
>>>>
>>>> /Flibble
>>>>
>>>
>>> To the best of my knowledge "side effect" is a software engineering term
>>> that has no application what-so-ever to the theory of computation. So
>>> far no one has been able to cite any source saying otherwise. On this
>>> basis I am tentatively concluding that you are simply wrong.
>>>
>>
>> The key is that you can't be using a 'side effect' (like a static
>> variable) to get around the requirements for being a Computation,
>> getting information from a source that isn't part of your inputs.
>>
>> It also means you can't change things that you aren't allowed to change,
>> like the stuff that 'called' you.
>>
> 
> A TM does whatever a TM does there is no sort of sanctioned behavior or
> unsanctioned behavior.
> 

A Turing Machine has a VERY defined process that it can execute. What it
can do is STRICTLY limited by that definition. For instance, a Turing
Machine can not start your car. That is NOT in its capability. You might
define some other abstract machine that processes the output of a Turing
Machine, and define that under certain conditions, to start your car.

Similarly, a Turing Machine can not affect the behavior of another
Turing Machine. The closest it gets is to 'simulate' a description of a
machine, and perhaps not exactly simulate it, but change the behavior.
This does NOT actually affect the Turing Machine whose description it is
simulating, only what the Turing Machine itself does.

This points out that Halts can't actually affect the ACTUAL operation of
any Turing Machine, only what it does to its simulation of one
internally to itself. That H_Hat machine will happily run on its own,
using a copy of Halts and using the answer it gives. (and because it is
a Turing Machine, the Halts that is in the Turing Machine H_Hat will
follow the rules of Turing Machines).

[toc] | [prev] | [next] | [standalone]


#32534

FromMr Flibble <flibble@i42.REMOVETHISBIT.co.uk>
Date2021-05-02 00:49 +0100
Message-ID<6OljI.314606$E75e.302358@fx21.ams4>
In reply to#32522
On 01/05/2021 23:32, olcott wrote:
> On 5/1/2021 4:42 PM, Mr Flibble wrote:
>> On 01/05/2021 20:09, olcott wrote:
>>> On 5/1/2021 1:55 PM, Richard Damon wrote:
>>>> On 5/1/21 1:40 PM, olcott wrote:
>>>>> On 5/1/2021 11:37 AM, 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.
>>>>>
>>>>>
>>>>> To make [computable function] generic to all models of computation:
>>>>> A [computable function] 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.
>>>>>
>>>>>
>>>> As I mentioned in my other reply, once you leave the domain of Turing
>>>> Machines, the requirement of a given input always giving the same output
>>>> becomes an important restriction, and a necessity for the operation to
>>>> be able to have a Turing Machine equivalent.
>>>>
>>>
>>> In the case of the mapping from Halts(H_Hat, H_Hat) to a final state 
>>> indicating "No" (not halting) it can perform any mechanical steps in any way 
>>> as long as the mapping from the input to the final state always produces the 
>>> same result.
>>>
>>> The part that you can never seem to understand is that between the start 
>>> state and the final state this machine is free to do anything that machines 
>>> can possibly do. You have never seemed to get this part.
>>
>> Nonsense. Any side effects over and above those allowed for a TM means we are 
>> no longer dealing with a TM.
>>
>> /Flibble
>>
> 
> To the best of my knowledge "side effect" is a software engineering term that 
> has no application what-so-ever to the theory of computation. So far no one has 
> been able to cite any source saying otherwise. On this basis I am tentatively 
> concluding that you are simply wrong.

I see. So if you want to ignore software engineering (computer science) even 
though that is the field to which the Halting Problem relates and stick to 
mathematics then in mathematics a function always returns the same output for a 
given input and that output includes any of the sneaky state you are trying to 
hide from us by sleight of hand.

/Flibble

-- 
😎

[toc] | [prev] | [next] | [standalone]


#32521

FromRichard Damon <Richard@Damon-Family.org>
Date2021-05-01 18:02 -0400
Message-ID<cekjI.88969$OF5.38235@fx07.iad>
In reply to#32511
On 5/1/21 3:09 PM, olcott wrote:
> On 5/1/2021 1:55 PM, Richard Damon wrote:
>> On 5/1/21 1:40 PM, olcott wrote:
>>> On 5/1/2021 11:37 AM, 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.
>>>
>>>
>>> To make [computable function] generic to all models of computation:
>>> A [computable function] 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.
>>>
>>>
>> As I mentioned in my other reply, once you leave the domain of Turing
>> Machines, the requirement of a given input always giving the same output
>> becomes an important restriction, and a necessity for the operation to
>> be able to have a Turing Machine equivalent.
>>
> 
> In the case of the mapping from Halts(H_Hat, H_Hat) to a final state
> indicating "No" (not halting) it can perform any mechanical steps in any
> way as long as the mapping from the input to the final state always
> produces the same result.
> 
> The part that you can never seem to understand is that between the start
> state and the final state this machine is free to do anything that
> machines can possibly do. You have never seemed to get this part.

Not 'Anything' as it is constrained by the definition of a Computation,
and as such it MUST return its answer to its caller. With those basic
requirements, we can show that we can make a Computation that it will
get its decision wrong on.

Find the error:

1) Halts is stipulated to meet the requirements of a Halt Decider for
Computation Theory, as used in the proof of Linz and Sipser.

2) Halts is stipulated to return non-Halting on Halts(H_Hat, H_Hat) when
asked direction (If you want to change that, we can give the other
argument for why that will be wrong)

3) H_Hat is stipulated to be built like Linz or Sipser, in that it will
halt when the Halt decider it is built on decides H_Hat’s input is
non-Halting on itself.

4) 1 Means that Halts is a Computation, and will always return the same
answer (or never return an answer) for a given input.

5) H_Hat when run as a Machine will perform the Computation Halts(H_Hat,
H_Hat)

6) by 4 and 2, this means that Halts will return the decision on
non-halting to H_Hat

7) By 3, this means that H_Hat will Halt.

8) This means that H_Hat is a Halting Computation, and because of 2,
Halts is wrong.

[toc] | [prev] | [next] | [standalone]


#32526

Fromolcott <NoOne@NoWhere.com>
Date2021-05-01 17:49 -0500
Message-ID<nZKdnfmsZvVQRxD9nZ2dnUU7-fvNnZ2d@giganews.com>
In reply to#32521
On 5/1/2021 5:02 PM, Richard Damon wrote:
> On 5/1/21 3:09 PM, olcott wrote:
>> On 5/1/2021 1:55 PM, Richard Damon wrote:
>>> On 5/1/21 1:40 PM, olcott wrote:
>>>> On 5/1/2021 11:37 AM, 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.
>>>>
>>>>
>>>> To make [computable function] generic to all models of computation:
>>>> A [computable function] 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.
>>>>
>>>>
>>> As I mentioned in my other reply, once you leave the domain of Turing
>>> Machines, the requirement of a given input always giving the same output
>>> becomes an important restriction, and a necessity for the operation to
>>> be able to have a Turing Machine equivalent.
>>>
>>
>> In the case of the mapping from Halts(H_Hat, H_Hat) to a final state
>> indicating "No" (not halting) it can perform any mechanical steps in any
>> way as long as the mapping from the input to the final state always
>> produces the same result.
>>
>> The part that you can never seem to understand is that between the start
>> state and the final state this machine is free to do anything that
>> machines can possibly do. You have never seemed to get this part.
> 
> Not 'Anything' as it is constrained by the definition of a Computation,
> and as such it MUST return its answer to its caller. With those basic
> requirements, we can show that we can make a Computation that it will
> get its decision wrong on.
> 
> Find the error:
> 
> 1) Halts is stipulated to meet the requirements of a Halt Decider for
> Computation Theory, as used in the proof of Linz and Sipser.

It halts in a final state indicating yes or no to the question does this 
input machine description finite string pair specify a finite computation.

> 
> 2) Halts is stipulated to return non-Halting on Halts(H_Hat, H_Hat) when
> asked direction (If you want to change that, we can give the other
> argument for why that will be wrong)

I understand what "asked direction means" for questions such as "which 
way to Walmart?" I have no idea what you are referring to by asked 
direction.

> 3) H_Hat is stipulated to be built like Linz or Sipser, in that it will
> halt when the Halt decider it is built on decides H_Hat’s input is
> non-Halting on itself.
Yes

> 4) 1 Means that Halts is a Computation, and will always return the same
> answer (or never return an answer) for a given input.
Yes.

> 5) H_Hat when run as a Machine will perform the Computation Halts(H_Hat,
> H_Hat)
Yes

> 6) by 4 and 2, this means that Halts will return the decision on
> non-halting to H_Hat
By (2)(4) and (5).


void H_Hat(u32 P)
{
   u32 Input_Halts = Halts(P, P);
   if (Input_Halts)
     HERE: goto HERE;
}


int main()
{
   H_Hat((u32)H_Hat);
}

> 7) By 3, this means that H_Hat will Halt.

The H_Hat in main() halts only because the H_Hat() simulated in H_Hat() 
is forced to halt on the basis that

Every computation that never stops unless its simulator stops simulating 
it <is> a non halting computation.

> 8) This means that H_Hat is a Halting Computation, and because of 2,
> Halts is wrong.

WRONG:
Every computation that never stops unless its simulator stops simulating 
it <is> a non halting computation.

If your reasoning was correct then when Halts() forces Infinite_Loop() 
to stop running this "proves" that Infinite_Loop() is not an infinite loop.

void Infinite_Loop()
{
   HERE: goto HERE;
}

int main()
{
   u32 Input_Would_Halt = Halts((u32)Infinite_Loop, (u32)Infinite_Loop);
}


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#32531

FromAndré G. Isaak <agisaak@gm.invalid>
Date2021-05-01 17:28 -0600
Message-ID<s6ko6l$g7u$1@dont-email.me>
In reply to#32526
On 2021-05-01 16:49, olcott wrote:

>> 7) By 3, this means that H_Hat will Halt.
> 
> The H_Hat in main() halts only because the H_Hat() simulated in H_Hat() 
> is forced to halt on the basis that
> 
> Every computation that never stops unless its simulator stops simulating 
> it <is> a non halting computation.
> 
>> 8) This means that H_Hat is a Halting Computation, and because of 2,
>> Halts is wrong.
> 
> WRONG:
> Every computation that never stops unless its simulator stops simulating 
> it <is> a non halting computation.

You really need to learn to be consistent with respect to the antecedent 
of 'its'. The H_Hat in main is the computation being asked about, and it 
doesn't *have* a simulator. Only the embedded H_Hat does, but that's an 
entirely different call. You're shifting the antecedent of 'its' from 
the actual computation under consideration to a call inside of it.

H_Hat halts not because some simulator stops it. It halts because it is 
a finite computation. The simulator *inside* H_Hat might stop simulating 
its input (which isn't the same as halting), but that's not what's being 
asked about.

André

> If your reasoning was correct then when Halts() forces Infinite_Loop() 
> to stop running this "proves" that Infinite_Loop() is not an infinite loop.
> 
> void Infinite_Loop()
> {
>    HERE: goto HERE;
> }
> 
> int main()
> {
>    u32 Input_Would_Halt = Halts((u32)Infinite_Loop, (u32)Infinite_Loop);
> }
> 
> 


-- 
To email remove 'invalid' & replace 'gm' with well known Google mail 
service.

[toc] | [prev] | [next] | [standalone]


#32533 — Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]

Fromolcott <NoOne@NoWhere.com>
Date2021-05-01 18:42 -0500
SubjectRe: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]
Message-ID<G8ydnSxUm8vFehD9nZ2dnUU7-IPNnZ2d@giganews.com>
In reply to#32531
On 5/1/2021 6:28 PM, André G. Isaak wrote:
> On 2021-05-01 16:49, olcott wrote:
> 
>>> 7) By 3, this means that H_Hat will Halt.
>>
>> The H_Hat in main() halts only because the H_Hat() simulated in 
>> H_Hat() is forced to halt on the basis that
>>
>> Every computation that never stops unless its simulator stops 
>> simulating it <is> a non halting computation.
>>
>>> 8) This means that H_Hat is a Halting Computation, and because of 2,
>>> Halts is wrong.
>>
>> WRONG:
>> Every computation that never stops unless its simulator stops 
>> simulating it <is> a non halting computation.
> 
> You really need to learn to be consistent with respect to the antecedent 
> of 'its'. The H_Hat in main is the computation being asked about, and it 
> doesn't *have* a simulator. Only the embedded H_Hat does, but that's an 
> entirely different call. You're shifting the antecedent of 'its' from 
> the actual computation under consideration to a call inside of it.
> 
> H_Hat halts not because some simulator stops it. It halts because it is 
> a finite computation. The simulator *inside* H_Hat might stop simulating 
> its input (which isn't the same as halting), but that's not what's being 
> asked about.

No H_Hat() in the universe ever stops running unless its otherwise 
infinite recursion is aborted at some point.

That this otherwise infinite recursion is aborted on its second call to 
the same function from the same machine address with the same data or 
the 13th time that this occurs makes no difference, H_Hat() ALWAYS 
specifies infinite recursion that must be aborted.


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#32536 — Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-05-02 01:51 +0100
SubjectRe: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]
Message-ID<87r1iq9cw6.fsf@bsb.me.uk>
In reply to#32533
olcott <NoOne@NoWhere.com> writes:

> No H_Hat() in the universe ever stops running unless its otherwise
> infinite recursion is aborted at some point.

This is just a silly word game.  What a computation would do "otherwise"
is irrelevant.  H_Hat(H_Hat) is finite and it does not matter how or
why.  It is a finite computation, and should be reported as such.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#32538 — Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]

Fromolcott <NoOne@NoWhere.com>
Date2021-05-01 20:05 -0500
SubjectRe: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]
Message-ID<cYKdnYdrW5VJZxD9nZ2dnUU7-Y2dnZ2d@giganews.com>
In reply to#32536
On 5/1/2021 7:51 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> 
>> No H_Hat() in the universe ever stops running unless its otherwise
>> infinite recursion is aborted at some point.
> 
> This is just a silly word game.  What a computation would do "otherwise"
> is irrelevant.  H_Hat(H_Hat) is finite and it does not matter how or
> why.  It is a finite computation, and should be reported as such.
> 

So in other words you believe that it is ridiculous for anyone to ever 
consider defining a partial halt decider because everyone agrees that is 
cannot be done perfectly so why bother doing this at all.

On the other hand there are only two possible choices for any partial 
halt decider:
(a) static analysis or
(b) dynamic analysis

that you reject dynamic analysis out-of-hand as "just silly" is a 
sufficiently strong indication that you have no interest in any honest 
dialogue.

-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#32540 — Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]

FromBen Bacarisse <ben.usenet@bsb.me.uk>
Date2021-05-02 02:20 +0100
SubjectRe: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]
Message-ID<87im429bie.fsf@bsb.me.uk>
In reply to#32538
olcott <NoOne@NoWhere.com> writes:

> On 5/1/2021 7:51 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> No H_Hat() in the universe ever stops running unless its otherwise
>>> infinite recursion is aborted at some point.
>>
>> This is just a silly word game.  What a computation would do "otherwise"
>> is irrelevant.  H_Hat(H_Hat) is finite and it does not matter how or
>> why.  It is a finite computation, and should be reported as such.
>
> So in other words you believe that it is ridiculous for anyone to ever
> consider defining a partial halt decider because everyone agrees that
> is cannot be done perfectly so why bother doing this at all.

No.  I am saying that your wording is silly because it attempts to
justify the wrong answer using another, different, computation.
H_Hat(H_Hat) is finite.  Halts(H_Hat, H_Hat) should be true, but you
have written Halts so that it's false and you justify that wrong answer
by what would happen were things not as they are.  It's flagrant
silliness.

When you find yourself starting off "So in other words you believe..."
you should stop and ask yourself, "what point am I trying to avoid by
putting words into my interlocutor's mount?".

-- 
Ben.

[toc] | [prev] | [next] | [standalone]


#32546 — Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]

Fromolcott <NoOne@NoWhere.com>
Date2021-05-01 20:42 -0500
SubjectRe: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]
Message-ID<pYudncz-SKL2nhP9nZ2dnUU7-f3NnZ2d@giganews.com>
In reply to#32540
On 5/1/2021 8:20 PM, Ben Bacarisse wrote:
> olcott <NoOne@NoWhere.com> writes:
> 
>> On 5/1/2021 7:51 PM, Ben Bacarisse wrote:
>>> olcott <NoOne@NoWhere.com> writes:
>>>
>>>> No H_Hat() in the universe ever stops running unless its otherwise
>>>> infinite recursion is aborted at some point.
>>>
>>> This is just a silly word game.  What a computation would do "otherwise"
>>> is irrelevant.  H_Hat(H_Hat) is finite and it does not matter how or
>>> why.  It is a finite computation, and should be reported as such.
>>
>> So in other words you believe that it is ridiculous for anyone to ever
>> consider defining a partial halt decider because everyone agrees that
>> is cannot be done perfectly so why bother doing this at all.
> 
> No.  I am saying that your wording is silly because it attempts to
> justify the wrong answer using another, different, computation.
> H_Hat(H_Hat) is finite. 

If the execution trace of function X() called by function Y() shows:
(1) Function X() is called twice in sequence from the same machine 
address of Y().
(2) With the same parameters to X().
(3) With no conditional branch or indexed jump instructions in Y().
(4) With no function call returns from X().
then the function call from Y() to X() is infinitely recursive.

The above criteria does correctly decide infinite recursion.
The above criteria does correctly decide infinite recursion.
The above criteria does correctly decide infinite recursion.

Every call from H_Hat() to Halts() meets this criteria.
Every call from H_Hat() to Halts() meets this criteria.
Every call from H_Hat() to Halts() meets this criteria.

Ignoring this key fact is no form of correct rebuttal.
Ignoring this key fact is no form of correct rebuttal.
Ignoring this key fact is no form of correct rebuttal.

> Halts(H_Hat, H_Hat) should be true, but you
> have written Halts so that it's false and you justify that wrong answer
> by what would happen were things not as they are.  It's flagrant
> silliness.

> When you find yourself starting off "So in other words you believe..."
> you should stop and ask yourself, "what point am I trying to avoid by
> putting words into my interlocutor's mount?".
> 


-- 
Copyright 2021 Pete Olcott

"Great spirits have always encountered violent opposition from mediocre 
minds." Einstein

[toc] | [prev] | [next] | [standalone]


#32549 — Re: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]

FromRichard Damon <Richard@Damon-Family.org>
Date2021-05-01 22:10 -0400
SubjectRe: Mutual agreement on the definition of a [computation] in computer science [ H_Hat() ALWAYS specifies infinite recursion that must be aborted ]
Message-ID<kSnjI.198903$2A5.42787@fx45.iad>
In reply to#32546
On 5/1/21 9:42 PM, olcott wrote:
> On 5/1/2021 8:20 PM, Ben Bacarisse wrote:
>> olcott <NoOne@NoWhere.com> writes:
>>
>>> On 5/1/2021 7:51 PM, Ben Bacarisse wrote:
>>>> olcott <NoOne@NoWhere.com> writes:
>>>>
>>>>> No H_Hat() in the universe ever stops running unless its otherwise
>>>>> infinite recursion is aborted at some point.
>>>>
>>>> This is just a silly word game.  What a computation would do
>>>> "otherwise"
>>>> is irrelevant.  H_Hat(H_Hat) is finite and it does not matter how or
>>>> why.  It is a finite computation, and should be reported as such.
>>>
>>> So in other words you believe that it is ridiculous for anyone to ever
>>> consider defining a partial halt decider because everyone agrees that
>>> is cannot be done perfectly so why bother doing this at all.
>>
>> No.  I am saying that your wording is silly because it attempts to
>> justify the wrong answer using another, different, computation.
>> H_Hat(H_Hat) is finite. 
> 
> If the execution trace of function X() called by function Y() shows:
> (1) Function X() is called twice in sequence from the same machine
> address of Y().
> (2) With the same parameters to X().
> (3) With no conditional branch or indexed jump instructions in Y().
> (4) With no function call returns from X().
> then the function call from Y() to X() is infinitely recursive.
> 
> The above criteria does correctly decide infinite recursion.
> 
> Every call from H_Hat() to Halts() meets this criteria.
> 
> Ignoring this key fact is no form of correct rebuttal.

First, H_Hat doesn't have an execution trace like that, as H_Hat 'calls'
Halts, and then Halts goes about simulating code and inspecting the trace.

That trace should see H_Hat 'call' Halts and Halts them simulating H_Hat.

There is no recursion.

Second, the traces that you do show that show a 'simulated' call from
the simulation end up ignoring the code in halts.

Also, since the function X called by function Y is really running as
part of the computation that Y is running, the fact that it can make a
decision to end what otherwise might be some form of infinite loop IS
part of the logic of Y, so Y gets 'credit' for it terminating the loop
and making things finite.

Thus your initial statement is incorrect.

IF the function call from Y to X is infinitely recursive, then so must
be the call from X to Y, and the execution of BOTH will be infinite,
i.e. non-halting. Mutual recursion can not be infinite on only one side.
If ANYTHING in the loop breaks it, it isn't infinite, thus the Y calling
X isn't infinite.

You Logic stinks.


> 
>> Halts(H_Hat, H_Hat) should be true, but you
>> have written Halts so that it's false and you justify that wrong answer
>> by what would happen were things not as they are.  It's flagrant
>> silliness.
> 
>> When you find yourself starting off "So in other words you believe..."
>> you should stop and ask yourself, "what point am I trying to avoid by
>> putting words into my interlocutor's mount?".
>>
> 
> 

[toc] | [prev] | [next] | [standalone]


Page 1 of 5  [1] 2 3 4 5  Next page →

Back to top | Article view | comp.theory


csiph-web