Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  newsreader  groups  login

Message-ID:  

Technology is dominated by those who manage what they do not understand.


devel / comp.theory / Re: Why do theory of computation problems require pure functions?

SubjectAuthor
* Why do theory of computation problems require pure functions?olcott
+- Why do theory of computation problems require pure functions?dklei...@gmail.com
+* Why do theory of computation problems require pure functions?André G. Isaak
|+* Why do theory of computation problems require pure functions?Jeff Barnett
||`* Why do theory of computation problems require pure functions?André G. Isaak
|| `- Why do theory of computation problems require pure functions?Jeff Barnett
|`* Why do theory of computation problems require pure functions?olcott
| +* Why do theory of computation problems require pure functions?Richard Damon
| |`* Why do theory of computation problems require pure functions?olcott
| | +* Why do theory of computation problems require pure functions?André G. Isaak
| | |+- Why do theory of computation problems require pure functions?olcott
| | |`* Why do theory of computation problems require pure functions?Richard Damon
| | | +* Why do theory of computation problems require pure functions?olcott
| | | |`* Why do theory of computation problems require pure functions?Richard Damon
| | | | `* Why do theory of computation problems require pure functions?olcott
| | | |  `* Why do theory of computation problems require pure functions?Richard Damon
| | | |   `- Why do theory of computation problems require pure functions?olcott
| | | `* Why do theory of computation problems require pure functions?André G. Isaak
| | |  `* Why do theory of computation problems require pure functions?Jeff Barnett
| | |   `* Why do theory of computation problems require pure functions?olcott
| | |    `* Why do theory of computation problems require pure functions?Richard Damon
| | |     `* Why do theory of computation problems require pure functions?olcott
| | |      `* Why do theory of computation problems require pure functions?Richard Damon
| | |       `* Why do theory of computation problems require pure functions?olcott
| | |        +* Why do theory of computation problems require pure functions?Ben Bacarisse
| | |        |`* Why do theory of computation problems require pure functions?olcott
| | |        | +- Why do theory of computation problems require pure functions?Richard Damon
| | |        | `- Why do theory of computation problems require pure functions?Ben Bacarisse
| | |        `- Why do theory of computation problems require pure functions?Richard Damon
| | `* Why do theory of computation problems require pure functions?Richard Damon
| |  `* Why do theory of computation problems require pure functions?olcott
| |   `* Why do theory of computation problems require pure functions?Richard Damon
| |    `* Why do theory of computation problems require pure functions?olcott
| |     `* Why do theory of computation problems require pure functions?Richard Damon
| |      `* Why do theory of computation problems require pure functions?olcott
| |       `* Why do theory of computation problems require pure functions?Richard Damon
| |        `* Why do theory of computation problems require pure functions?olcott
| |         `* Why do theory of computation problems require pure functions?Richard Damon
| |          `* Why do theory of computation problems require pure functions?Ben Bacarisse
| |           `* Why do theory of computation problems require pure functions?olcott
| |            +- Why do theory of computation problems require pure functions?Richard Damon
| |            `- Why do theory of computation problems require pure functions?Ben Bacarisse
| `* Why do theory of computation problems require pure functions?André G. Isaak
|  `* Why do theory of computation problems require pure functions?olcott
|   `* Why do theory of computation problems require pure functions?André G. Isaak
|    `- Why do theory of computation problems require pure functions?olcott
+- Why do theory of computation problems require pure functions?Richard Damon
`* Why do theory of computation problems require pure functions?Andy Walker
 +* Why do theory of computation problems require pure functions?olcott
 |+- Why do theory of computation problems require pure functions?Richard Damon
 |`* Why do theory of computation problems require pure functions?André G. Isaak
 | `* Why do theory of computation problems require pure functions?olcott
 |  +* Why do theory of computation problems require pure functions?Richard Damon
 |  |`* Why do theory of computation problems require pure functions?olcott
 |  | +* Why do theory of computation problems require pure functions?Richard Damon
 |  | |`* Why do theory of computation problems require pure functions?olcott
 |  | | `* Why do theory of computation problems require pure functions?Richard Damon
 |  | |  `* Why do theory of computation problems require pure functions?olcott
 |  | |   `* Why do theory of computation problems require pure functions?Richard Damon
 |  | |    `* Why do theory of computation problems require pure functions?olcott
 |  | |     `* Why do theory of computation problems require pure functions?Richard Damon
 |  | |      `* Why do theory of computation problems require pure functions?olcott
 |  | |       `* Why do theory of computation problems require pure functions?Richard Damon
 |  | |        `* Why do theory of computation problems require pure functions?olcott
 |  | |         `* Why do theory of computation problems require pure functions?Richard Damon
 |  | |          `* Why do theory of computation problems require pure functions?olcott
 |  | |           `* Why do theory of computation problems require pure functions?Richard Damon
 |  | |            `* Why do theory of computation problems require pure functions?olcott
 |  | |             `* Why do theory of computation problems require pure functions?Richard Damon
 |  | |              `* Why do theory of computation problems require pure functions?olcott
 |  | |               `- Why do theory of computation problems require pure functions?Richard Damon
 |  | `- Why do theory of computation problems require pure functions?Ben Bacarisse
 |  +* Why do theory of computation problems require pure functions?André G. Isaak
 |  |`* Why do theory of computation problems require pure functions?olcott
 |  | +* Why do theory of computation problems require pure functions?André G. Isaak
 |  | |`* Why do theory of computation problems require pure functions?olcott
 |  | | `* Why do theory of computation problems require pure functions?Richard Damon
 |  | |  `* Why do theory of computation problems require pure functions?olcott
 |  | |   +* Why do theory of computation problems require pure functions?Richard Damon
 |  | |   |`* Why do theory of computation problems require pure functions?olcott
 |  | |   | `* Why do theory of computation problems require pure functions?Richard Damon
 |  | |   |  `* Why do theory of computation problems require pure functions?olcott
 |  | |   |   +- Why do theory of computation problems require pure functions?Richard Damon
 |  | |   |   `* Why do theory of computation problems require pure functions?André G. Isaak
 |  | |   |    `* Why do theory of computation problems require pure functions?olcott
 |  | |   |     +* Why do theory of computation problems require pure functions?André G. Isaak
 |  | |   |     |`* Why do theory of computation problems require pure functions?olcott
 |  | |   |     | +* Why do theory of computation problems require pure functions?André G. Isaak
 |  | |   |     | |+- Why do theory of computation problems require pure functions?Richard Damon
 |  | |   |     | |+* Why do theory of computation problems require pure functions?olcott
 |  | |   |     | ||+* Why do theory of computation problems require pure functions?Richard Damon
 |  | |   |     | |||`* Why do theory of computation problems require pure functions?olcott
 |  | |   |     | ||| +* Why do theory of computation problems require pure functions?André G. Isaak
 |  | |   |     | ||| |`* Why do theory of computation problems require pure functions?André G. Isaak
 |  | |   |     | ||| | +* Why do theory of computation problems require pure functions?olcott
 |  | |   |     | ||| | |+* Why do theory of computation problems require pure functions?André G. Isaak
 |  | |   |     | ||| | ||`* Why do theory of computation problems require pure functions?[ decidability deciolcott
 |  | |   |     | ||| | || `- Why do theory of computation problems require pure functions?[André G. Isaak
 |  | |   |     | ||| | |`- Why do theory of computation problems require pure functions?Richard Damon
 |  | |   |     | ||| | `* Why do theory of computation problems require pure functions?olcott
 |  | |   |     | ||| |  `* Why do theory of computation problems require pure functions?André G. Isaak
 |  | |   |     | ||| `- Why do theory of computation problems require pure functions?Richard Damon
 |  | |   |     | ||`- Why do theory of computation problems require pure functions?André G. Isaak
 |  | |   |     | |`* Why do theory of computation problems require pure functions?Malcolm McLean
 |  | |   |     | `* Why do theory of computation problems require pure functions?Jeff Barnett
 |  | |   |     `- Why do theory of computation problems require pure functions?Richard Damon
 |  | |   `* Why do theory of computation problems require pure functions?Ben Bacarisse
 |  | `* Why do theory of computation problems require pure functions?Richard Damon
 |  `* Why do theory of computation problems require pure functions?Ben Bacarisse
 `* Why do theory of computation problems require pure functions?Ben Bacarisse

Pages:12345678910
Why do theory of computation problems require pure functions?

<a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=21266&group=comp.theory#21266

 copy link   Newsgroups: comp.theory comp.ai.philosophy sci.logic sci.math
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 17 Sep 2021 21:40:09 -0500
Newsgroups: comp.theory,comp.ai.philosophy,sci.logic,sci.math
X-Mozilla-News-Host: news://news.giganews.com:119
From: NoO...@NoWhere.com (olcott)
Subject: Why do theory of computation problems require pure functions?
Date: Fri, 17 Sep 2021 21:40:09 -0500
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.14.0
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Message-ID: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>
Lines: 23
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-GZ8BBpnoSr4EnH908hCpre+c5mCskoj8RMbS9f2+rikpDxYpNC3uyBdShVRBv1HltRX//b7jD9MXMqf!rymZd6XanUR5AvwOEcgTu6DCmucBi2saPKVxTLK9zP/woy67irPLglkcz17XXhyEm4uum+u0VS+I!4ks=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 2032
 by: olcott - Sat, 18 Sep 2021 02:40 UTC

Why do theory of computation problems require pure functions?

I am trying to write C code that would be acceptable to computer
scientists in the field of the theory of computation.

In computer programming, a pure function is a function that has the
following properties:

(1) The function return values are identical for identical arguments (no
variation with local static variables, non-local variables, mutable
reference arguments or input streams).

(2) The function application has no side effects (no mutation of local
static variables, non-local variables, mutable reference arguments or
input/output streams).

https://en.wikipedia.org/wiki/Pure_function#Compiler_optimizations

--
Copyright 2021 Pete Olcott

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

Re: Why do theory of computation problems require pure functions?

<8b1f131c-60ac-4ed2-af24-17814049107an@googlegroups.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=21267&group=comp.theory#21267

 copy link   Newsgroups: comp.theory
X-Received: by 2002:a05:620a:81c:: with SMTP id s28mr13551264qks.45.1631940507211;
Fri, 17 Sep 2021 21:48:27 -0700 (PDT)
X-Received: by 2002:a25:5246:: with SMTP id g67mr16941812ybb.56.1631940507054;
Fri, 17 Sep 2021 21:48:27 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!proxad.net!feeder1-2.proxad.net!209.85.160.216.MISMATCH!news-out.google.com!nntp.google.com!postnews.google.com!google-groups.googlegroups.com!not-for-mail
Newsgroups: comp.theory
Date: Fri, 17 Sep 2021 21:48:26 -0700 (PDT)
In-Reply-To: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>
Injection-Info: google-groups.googlegroups.com; posting-host=47.208.130.96; posting-account=7Xc2EwkAAABXMcQfERYamr3b-64IkBws
NNTP-Posting-Host: 47.208.130.96
References: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>
User-Agent: G2/1.0
MIME-Version: 1.0
Message-ID: <8b1f131c-60ac-4ed2-af24-17814049107an@googlegroups.com>
Subject: Re: Why do theory of computation problems require pure functions?
From: dkleine...@gmail.com (dklei...@gmail.com)
Injection-Date: Sat, 18 Sep 2021 04:48:27 +0000
Content-Type: text/plain; charset="UTF-8"
 by: dklei...@gmail.com - Sat, 18 Sep 2021 04:48 UTC

On Friday, September 17, 2021 at 7:40:17 PM UTC-7, olcott wrote:
> Why do theory of computation problems require pure functions?
>
> I am trying to write C code that would be acceptable to computer
> scientists in the field of the theory of computation.
>
> In computer programming, a pure function is a function that has the
> following properties:
>
> (1) The function return values are identical for identical arguments (no
> variation with local static variables, non-local variables, mutable
> reference arguments or input streams).
>
> (2) The function application has no side effects (no mutation of local
> static variables, non-local variables, mutable reference arguments or
> input/output streams).
>
> https://en.wikipedia.org/wiki/Pure_function#Compiler_optimizations
It is possible that a rigorous theory of computation based on the
assumptions associated with computer scientists could be developed
but until then we have the mathematical theory where a function is a set
F of ordered pairs such that if [a, x] and [a, y] both belong to F then x = y.

Re: Why do theory of computation problems require pure functions?

<si3r5q$8ln$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=21268&group=comp.theory#21268

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: agis...@gm.invalid (André G. Isaak)
Newsgroups: comp.theory
Subject: Re: Why do theory of computation problems require pure functions?
Date: Fri, 17 Sep 2021 22:50:01 -0600
Organization: Christians and Atheists United Against Creeping Agnosticism
Lines: 35
Message-ID: <si3r5q$8ln$1@dont-email.me>
References: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 18 Sep 2021 04:50:02 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="b2780b02a2648bf8f0dad6d21eb6aca0";
logging-data="8887"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/CYon+fDOZ9qsMeb6jaLbX"
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:68.0)
Gecko/20100101 Thunderbird/68.12.1
Cancel-Lock: sha1:wCgv+u/U/1h/x/pgbk1gMxkaJ24=
In-Reply-To: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>
Content-Language: en-US
 by: André G. Isaak - Sat, 18 Sep 2021 04:50 UTC

On 2021-09-17 20:40, olcott wrote:
> Why do theory of computation problems require pure functions?

Because the theory of computation isn't about C or x86. It isn't about
computer programs at all, nor about modern computers. Just because
'computation' and 'computer' share the same root doesn't mean they deal
with the same set of phenomena. Remember that the theory of computation
developed before there even were digital computers or programming languages.

Computational theory is concerned with describing *mathematical*
functions, and all mathematical functions are pure functions. A
computation is a method for determining the value of the mathematical
function f(x) for a given x. A computable function is one for which it
is possible to construct a TM which, given an input string representing
x, will determine the value of f(x).

You can write computer programs which perform computations, but the
majority of computer programs don't.

If you really want to learn about the theory of computation, I'd suggest
that you forget about C or x86 assembly or any sort of computer language
altogether and focus on Turing Machines.

And don't try to mentally translate anything you read about Turing
Machines into computer languages. Don't think about loop counters, or
calls, or machine addresses, because all of these things pertain to
computers and computer programming rather than computations and they
will get in the way of you actually understanding either turing machines
or the theory of computation more generally.

André

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

Re: Why do theory of computation problems require pure functions?

<si3ven$s2l$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=21269&group=comp.theory#21269

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: jbb...@notatt.com (Jeff Barnett)
Newsgroups: comp.theory
Subject: Re: Why do theory of computation problems require pure functions?
Date: Sat, 18 Sep 2021 00:02:57 -0600
Organization: A noiseless patient Spider
Lines: 74
Message-ID: <si3ven$s2l$1@dont-email.me>
References: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>
<si3r5q$8ln$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: quoted-printable
Injection-Date: Sat, 18 Sep 2021 06:03:04 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="1b7827382ecccdf8c22e95591d3f0932";
logging-data="28757"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+LBh69I7ecr1CsMZQJWYuhExzOaiNrhrU="
User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.14.0
Cancel-Lock: sha1:tEhzAN7bnN3cYEqJFV6C79LVhck=
In-Reply-To: <si3r5q$8ln$1@dont-email.me>
Content-Language: en-US
 by: Jeff Barnett - Sat, 18 Sep 2021 06:02 UTC

On 9/17/2021 10:50 PM, André G. Isaak wrote:
> On 2021-09-17 20:40, olcott wrote:
>> Why do theory of computation problems require pure functions?
>
> Because the theory of computation isn't about C or x86. It isn't about
> computer programs at all, nor about modern computers. Just because
> 'computation' and 'computer' share the same root doesn't mean they deal
> with the same set of phenomena. Remember that the theory of computation
> developed before there even were digital computers or programming
> languages.
>
> Computational theory is concerned with describing *mathematical*
> functions, and all mathematical functions are pure functions. A
> computation is a method for determining the value of the mathematical
> function f(x) for a given x. A computable function is one for which it
> is possible to construct a TM which, given an input string representing
> x, will determine the value of f(x).
>
> You can write computer programs which perform computations, but the
> majority of computer programs don't.
>
> If you really want to learn about the theory of computation, I'd suggest
> that you forget about C or x86 assembly or any sort of computer language
> altogether and focus on Turing Machines.
>
> And don't try to mentally translate anything you read about Turing
> Machines into computer languages. Don't think about loop counters, or
> calls, or machine addresses, because all of these things pertain to
> computers and computer programming rather than computations and they
> will get in the way of you actually understanding either turing machines
> or the theory of computation more generally.
What you say is conventional wisdom as far as you went. It should,
however, be added that there is a glut of theoretical work on real
aspects of computation (perhaps that should be aspects of real
computations!). In any event, there is enormous literature, mathematics,
and models for parallel computation, reals time control, et al. These
systems don't resemble our pristine math models such in Linz. However,
some of that theoretical work shows how one can extend the TM "model" to
include connectivity with a random environment, continuous operating
controllers, and on and on. None of these extended models really gain
any power or allow new computations what ever we might mean by computation.

So does the current theory of computation require "pure functions"? No
it doesn't. However, since playing with TMs in these extended domains
gains nothing, studying basic properties such as halting goes from
fairly simple to being a royal pain in the ass.

In reality you draw a perimeter around some computational components and
study such systems with various constraints on what you can put inside.
The outside of the perimeter can be virtually nonexistent as when
studying an ordinary TM or it can be quite complex when all you have is
a probabilistic model. By the way, systems in the latter category
include real time controllers and these systems are probably the most
thoroughly tested software in existence (avionics, nuclear power, etc.).
In those case where the environment is probabilistic or the computation
is nondeterministic in some way, one needs to define how the system's
behavior is determined: any path to a final state or probability density
over results, etc.
--
Jeff Barnett

Re: Why do theory of computation problems require pure functions?

<si402n$v4c$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=21270&group=comp.theory#21270

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: agis...@gm.invalid (André G. Isaak)
Newsgroups: comp.theory
Subject: Re: Why do theory of computation problems require pure functions?
Date: Sat, 18 Sep 2021 00:13:41 -0600
Organization: Christians and Atheists United Against Creeping Agnosticism
Lines: 13
Message-ID: <si402n$v4c$1@dont-email.me>
References: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>
<si3r5q$8ln$1@dont-email.me> <si3ven$s2l$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 18 Sep 2021 06:13:43 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="b2780b02a2648bf8f0dad6d21eb6aca0";
logging-data="31884"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18NcLTMrkBCXe/EvDnt34Ec"
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:68.0)
Gecko/20100101 Thunderbird/68.12.1
Cancel-Lock: sha1:LJ5QDsQgDUBeBiP6rS3Tp8gY8K4=
In-Reply-To: <si3ven$s2l$1@dont-email.me>
Content-Language: en-US
 by: André G. Isaak - Sat, 18 Sep 2021 06:13 UTC

On 2021-09-18 00:02, Jeff Barnett wrote:

> What you say is conventional wisdom as far as you went. It should,
> however, be added that there is a glut of theoretical work on real
> aspects of computation (perhaps that should be aspects of real
> computations!).
Quite right, but Olcott needs to learn to walk before he tries to run.

André

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

Re: Why do theory of computation problems require pure functions?

<si4110$3l1$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=21271&group=comp.theory#21271

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: jbb...@notatt.com (Jeff Barnett)
Newsgroups: comp.theory
Subject: Re: Why do theory of computation problems require pure functions?
Date: Sat, 18 Sep 2021 00:29:48 -0600
Organization: A noiseless patient Spider
Lines: 12
Message-ID: <si4110$3l1$1@dont-email.me>
References: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>
<si3r5q$8ln$1@dont-email.me> <si3ven$s2l$1@dont-email.me>
<si402n$v4c$1@dont-email.me>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: quoted-printable
Injection-Date: Sat, 18 Sep 2021 06:29:52 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="1b7827382ecccdf8c22e95591d3f0932";
logging-data="3745"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1/FPdNVVKpweFJ/RA8D5nSJvQjbMGg6uhA="
User-Agent: Mozilla/5.0 (Windows NT 6.1; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.14.0
Cancel-Lock: sha1:a+dym+O8TeVhZB2lTpTN3DnJ/qk=
In-Reply-To: <si402n$v4c$1@dont-email.me>
Content-Language: en-US
 by: Jeff Barnett - Sat, 18 Sep 2021 06:29 UTC

On 9/18/2021 12:13 AM, André G. Isaak wrote:
> On 2021-09-18 00:02, Jeff Barnett wrote:
>
>> What you say is conventional wisdom as far as you went. It should,
>> however, be added that there is a glut of theoretical work on real
>> aspects of computation (perhaps that should be aspects of real
>> computations!).
> Quite right, but Olcott needs to learn to walk before he tries to run.
Right but crawl is closer to the mark.
--
Jeff Barnett

Re: Why do theory of computation problems require pure functions?

<dSj1J.10135$mg5.470@fx26.iad>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=21272&group=comp.theory#21272

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!aioe.org!news.uzoreto.com!tr2.eu1.usenetexpress.com!feeder.usenetexpress.com!tr1.iad1.usenetexpress.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!fx26.iad.POSTED!not-for-mail
Subject: Re: Why do theory of computation problems require pure functions?
Newsgroups: comp.theory
References: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>
From: Rich...@Damon-Family.org (Richard Damon)
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:78.0) Gecko/20100101 Thunderbird/78.14.0
MIME-Version: 1.0
In-Reply-To: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Lines: 52
Message-ID: <dSj1J.10135$mg5.470@fx26.iad>
X-Complaints-To: abuse@easynews.com
Organization: Forte - www.forteinc.com
X-Complaints-Info: Please be sure to forward a copy of ALL headers otherwise we will be unable to process your complaint properly.
Date: Sat, 18 Sep 2021 07:14:16 -0400
X-Received-Bytes: 3164
 by: Richard Damon - Sat, 18 Sep 2021 11:14 UTC

On 9/17/21 10:40 PM, olcott wrote:
> Why do theory of computation problems require pure functions?
>
> I am trying to write C code that would be acceptable to computer
> scientists in the field of the theory of computation.
>
> In computer programming, a pure function is a function that has the
> following properties:
>
> (1) The function return values are identical for identical arguments (no
> variation with local static variables, non-local variables, mutable
> reference arguments or input streams).
>
> (2) The function application has no side effects (no mutation of local
> static variables, non-local variables, mutable reference arguments or
> input/output streams).
>
> https://en.wikipedia.org/wiki/Pure_function#Compiler_optimizations
>

Good Question!

The key thing to understand is that the Theory of Computations isn't
really about what computers can do, at least not in the 'modern' sense.
But is about basic mathematics, and limits of what is knowable.

In Mathematics, they started with a definition of a function, as a
mapping of input values to output values, with the output value fully
defined by the input. (This is where the computer term 'Pure' Function
comes from, it is a computer function that matches the mathematical
definition).

The next question that came up, can we actually calculate what this
function is for a given input? Some problems are easy to calculate, like
how many ways can you order N distinct items. Some can't be easily
answered, maybe requiring a form of exhaustive searching that you might
not actually be sure you would be able to get an answer.

This gets us into the question of is the function 'Computible', meaning
could someone with a 'formula' or an 'algorithm' be able to calculate
the value of the function in a finite amount of time.

This is the problem field of Computation Theory, looking at what things
can be computed by that sort of method, and some estimates of how long
it might take (complexity theory)

It doesn't directly relate to the 'Modern Computer' and its programming,
except to the extent that the modern computer was created to get these
answers by following those algorithms.

So, Computation Theory wants 'pure functions' because that is what the
field was built on.

Re: Why do theory of computation problems require pure functions?

<si4khe$1nvt$1@gioia.aioe.org>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=21273&group=comp.theory#21273

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!aioe.org!k03buBvHr7vkGaN2ImDPQQ.user.46.165.242.75.POSTED!not-for-mail
From: anw...@cuboid.co.uk (Andy Walker)
Newsgroups: comp.theory
Subject: Re: Why do theory of computation problems require pure functions?
Date: Sat, 18 Sep 2021 13:02:53 +0100
Organization: Not very much
Message-ID: <si4khe$1nvt$1@gioia.aioe.org>
References: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Info: gioia.aioe.org; logging-data="57341"; posting-host="k03buBvHr7vkGaN2ImDPQQ.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Mozilla/5.0 (X11; Linux i686; rv:78.0) Gecko/20100101
Thunderbird/78.13.0
Content-Language: en-GB
X-Notice: Filtered by postfilter v. 0.9.2
 by: Andy Walker - Sat, 18 Sep 2021 12:02 UTC

On 18/09/2021 03:40, olcott wrote:
> Why do theory of computation problems require pure functions?

This hasn't yet had a good answer. IMO, they don't. But
they do require a level of abstraction that you have thus far been
trying to evade. Problems require solutions, not "Well, it could
be /this/, or perhaps /that/ or on the other hand, especially on
the Monday of a full moon, /something else/. The HP requires us
to say, of a program/input pair, "this instance terminates" or
"this instance doesn't terminate", not "well, it might if ...".
What normally has to be "pure" in a "computation problem" is the
program, not individual bits thereof. ...

> I am trying to write C code that would be acceptable to computer
> scientists in the field of the theory of computation.

... Then write it and stop worrying. But you have become
mired in levels of simulation and [alleged] recursion. A C program
describes an abstract machine, as defined [not all that well, but
well enough for our purposes] by the C Standard [qv]. Either work
within that abstract machine, or extend it in ways that you can
define [eg, to have arbitrarily large integers]. But if you want
to apply this program/machine to [eg] the "Linz proof", then you
need to remember that the edited program/machine that produces
the contradiction is not an edit of part of your code, but an
edit of the entire program/machine. That is why people have been
jumping all over your arguments and saying "But ..., but ..., but
...." and going on about purity and computations.

Incidentally, please, pretty please, forget about 386
machine code. It really, really doesn't help. It just obscures
whatever argument you're trying to make. Indeed, it gives the
impression that obscurity is what you want [which may, of course,
be the case, but if so then stop wasting everyone's time].

--
Andy Walker, Nottingham.
Andy's music pages: www.cuboid.me.uk/andy/Music
Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Hummel

Re: Why do theory of computation problems require pure functions?

<KZSdncvVqtDkctj8nZ2dnUU7-f_NnZ2d@giganews.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=21274&group=comp.theory#21274

 copy link   Newsgroups: comp.theory comp.ai.philosophy sci.logic sci.math
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sat, 18 Sep 2021 08:54:01 -0500
Subject: Re: Why do theory of computation problems require pure functions?
Newsgroups: comp.theory,comp.ai.philosophy,sci.logic,sci.math
References: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>
<si3r5q$8ln$1@dont-email.me>
From: NoO...@NoWhere.com (olcott)
Date: Sat, 18 Sep 2021 08:54:00 -0500
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.14.0
MIME-Version: 1.0
In-Reply-To: <si3r5q$8ln$1@dont-email.me>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <KZSdncvVqtDkctj8nZ2dnUU7-f_NnZ2d@giganews.com>
Lines: 54
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-TqTHw2S+laJZwkNKk95W2qHFjK+pJMLJ9p84r54AeodOem2rmSkbCn+D5xV77U2PkHBPEulPJ4gdcOf!ofVKbXOqh1XG++Q14wSFMjoCWJqLAjs6HvFCR/bQfyFOfQ4CEhIuL9srWD+LW4pcBcLSPWO7fasd!12w=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 3736
 by: olcott - Sat, 18 Sep 2021 13:54 UTC

On 9/17/2021 11:50 PM, André G. Isaak wrote:
> On 2021-09-17 20:40, olcott wrote:
>> Why do theory of computation problems require pure functions?
>
> Because the theory of computation isn't about C or x86. It isn't about
> computer programs at all, nor about modern computers. Just because
> 'computation' and 'computer' share the same root doesn't mean they deal
> with the same set of phenomena. Remember that the theory of computation
> developed before there even were digital computers or programming
> languages.
>
> Computational theory is concerned with describing *mathematical*
> functions, and all mathematical functions are pure functions. A
> computation is a method for determining the value of the mathematical
> function f(x) for a given x. A computable function is one for which it
> is possible to construct a TM which, given an input string representing
> x, will determine the value of f(x).
>
> You can write computer programs which perform computations, but the
> majority of computer programs don't.
>
> If you really want to learn about the theory of computation, I'd suggest
> that you forget about C or x86 assembly or any sort of computer language
> altogether and focus on Turing Machines.
>
> And don't try to mentally translate anything you read about Turing
> Machines into computer languages. Don't think about loop counters, or
> calls, or machine addresses, because all of these things pertain to
> computers and computer programming rather than computations and they
> will get in the way of you actually understanding either turing machines
> or the theory of computation more generally.
>
> André
>

I only need to know this for one reason.

When my halt decider is examining the behavior of its input and the
input calls this halt decider in infinite recursion it cannot keep track
of the behavior of this input without having a single pseudo static
variable that is directly embedded in its machine code.

This pseudo static variable stores the ongoing execution trace. When the
variable is an ordinary local variable it loses all of its data between
each recursive simulation.

It still seems to be a pure function of its input in that
(1) The function return values are identical for identical arguments

--
Copyright 2021 Pete Olcott

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

Re: Why do theory of computation problems require pure functions?

<mJmdnfaWlv7Kbdj8nZ2dnUU7-YHNnZ2d@giganews.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=21275&group=comp.theory#21275

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!aioe.org!feeder1.feed.usenet.farm!feed.usenet.farm!tr3.eu1.usenetexpress.com!feeder.usenetexpress.com!tr1.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sat, 18 Sep 2021 08:57:43 -0500
Subject: Re: Why do theory of computation problems require pure functions?
Newsgroups: comp.theory
References: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com> <si4khe$1nvt$1@gioia.aioe.org>
From: NoO...@NoWhere.com (olcott)
Date: Sat, 18 Sep 2021 08:57:41 -0500
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.14.0
MIME-Version: 1.0
In-Reply-To: <si4khe$1nvt$1@gioia.aioe.org>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <mJmdnfaWlv7Kbdj8nZ2dnUU7-YHNnZ2d@giganews.com>
Lines: 47
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-A9bLx3zriDaJ6skxr+snGFzXekJalQi/f0Iw4Gmzpl6v6WvXJFnkt/J7A9lhkuryStCrdbycmYui5BZ!/aKVTu+qg6yVcVED1QrWv28NbMPyaI33RshI9W2v4Hg4C9NrT1gLae5BAZLCdaG5VHGm5ODM4oUq!1h8=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 3689
 by: olcott - Sat, 18 Sep 2021 13:57 UTC

On 9/18/2021 7:02 AM, Andy Walker wrote:
> On 18/09/2021 03:40, olcott wrote:
>> Why do theory of computation problems require pure functions?
>
>     This hasn't yet had a good answer.  IMO, they don't.  But
> they do require a level of abstraction that you have thus far been
> trying to evade.  Problems require solutions, not "Well, it could
> be /this/, or perhaps /that/ or on the other hand, especially on
> the Monday of a full moon, /something else/.  The HP requires us
> to say, of a program/input pair, "this instance terminates" or
> "this instance doesn't terminate", not "well, it might if ...".
> What normally has to be "pure" in a "computation problem" is the
> program, not individual bits thereof. ...
>
>> I am trying to write C code that would be acceptable to computer
>> scientists in the field of the theory of computation.
>
>     ... Then write it and stop worrying.  But you have become
> mired in levels of simulation and [alleged] recursion.  A C program
> describes an abstract machine, as defined [not all that well, but
> well enough for our purposes] by the C Standard [qv].  Either work
> within that abstract machine, or extend it in ways that you can
> define [eg, to have arbitrarily large integers].  But if you want
> to apply this program/machine to [eg] the "Linz proof", then you
> need to remember that the edited program/machine that produces
> the contradiction is not an edit of part of your code, but an
> edit of the entire program/machine.  That is why people have been
> jumping all over your arguments and saying "But ..., but ..., but
> ..." and going on about purity and computations.
>
>     Incidentally, please, pretty please, forget about 386
> machine code.  It really, really doesn't help.  It just obscures
> whatever argument you're trying to make.  Indeed, it gives the
> impression that obscurity is what you want [which may, of course,
> be the case, but if so then stop wasting everyone's time].
>

I either must stick with C/x86 code or write a RASP machine, the only
way that my key insights can possible be fully understood is to have
every single detail as fully operational code such that we can simply
see what it does and thus not merely imagine what it would do.

--
Copyright 2021 Pete Olcott

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

Re: Why do theory of computation problems require pure functions?

<ZVm1J.3937$7U3.2717@fx24.iad>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=21276&group=comp.theory#21276

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!paganini.bofh.team!news.dns-netz.com!news.freedyn.net!newsreader4.netcologne.de!news.netcologne.de!peer02.ams1!peer.ams1.xlned.com!news.xlned.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!fx24.iad.POSTED!not-for-mail
Subject: Re: Why do theory of computation problems require pure functions?
Newsgroups: comp.theory
References: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>
<si3r5q$8ln$1@dont-email.me> <KZSdncvVqtDkctj8nZ2dnUU7-f_NnZ2d@giganews.com>
From: Rich...@Damon-Family.org (Richard Damon)
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:78.0)
Gecko/20100101 Thunderbird/78.14.0
MIME-Version: 1.0
In-Reply-To: <KZSdncvVqtDkctj8nZ2dnUU7-f_NnZ2d@giganews.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Lines: 101
Message-ID: <ZVm1J.3937$7U3.2717@fx24.iad>
X-Complaints-To: abuse@easynews.com
Organization: Forte - www.forteinc.com
X-Complaints-Info: Please be sure to forward a copy of ALL headers otherwise we will be unable to process your complaint properly.
Date: Sat, 18 Sep 2021 10:43:04 -0400
X-Received-Bytes: 6124
 by: Richard Damon - Sat, 18 Sep 2021 14:43 UTC

On 9/18/21 9:54 AM, olcott wrote:
> On 9/17/2021 11:50 PM, André G. Isaak wrote:
>> On 2021-09-17 20:40, olcott wrote:
>>> Why do theory of computation problems require pure functions?
>>
>> Because the theory of computation isn't about C or x86. It isn't about
>> computer programs at all, nor about modern computers. Just because
>> 'computation' and 'computer' share the same root doesn't mean they
>> deal with the same set of phenomena. Remember that the theory of
>> computation developed before there even were digital computers or
>> programming languages.
>>
>> Computational theory is concerned with describing *mathematical*
>> functions, and all mathematical functions are pure functions. A
>> computation is a method for determining the value of the mathematical
>> function f(x) for a given x. A computable function is one for which it
>> is possible to construct a TM which, given an input string
>> representing x, will determine the value of f(x).
>>
>> You can write computer programs which perform computations, but the
>> majority of computer programs don't.
>>
>> If you really want to learn about the theory of computation, I'd
>> suggest that you forget about C or x86 assembly or any sort of
>> computer language altogether and focus on Turing Machines.
>>
>> And don't try to mentally translate anything you read about Turing
>> Machines into computer languages. Don't think about loop counters, or
>> calls, or machine addresses, because all of these things pertain to
>> computers and computer programming rather than computations and they
>> will get in the way of you actually understanding either turing
>> machines or the theory of computation more generally.
>>
>> André
>>
>
> I only need to know this for one reason.
>
> When my halt decider is examining the behavior of its input and the
> input calls this halt decider in infinite recursion it cannot keep track
> of the behavior of this input without having a single pseudo static
> variable that is directly embedded in its machine code.
>
> This pseudo static variable stores the ongoing execution trace. When the
> variable is an ordinary local variable it loses all of its data between
> each recursive simulation.
>
> It still seems to be a pure function of its input in that
> (1) The function return values are identical for identical arguments
>

I think the key issue is that if you want to talk about the plain
behavior of C / x86 code, then you need to talk about the ACTUAL
behavior of that code, which means that the call to H within the
simulated machine needs to be seen as a call to H, and NOT some logical
transformation.

If you want to do the transformation, your need to actually PROVE that
this transform is legitimate under the conditions you want to make it,
and that needs a very FORMAL argument based on accepted truths and
principles. Your 'argument' based on H not affecting P until after it
makes its decision so it can ignore its effect, is one of those
arguments that just seems 'obvious' but you haven't actually proved it.
You don't seem to uhderstand that nature of how to prove something like
this.

'Obvious' things can be wrong, like it seems obvious that the order you
add up a series shouldn't affect the result, even if the number of terms
in infinite, but there are simple proofs to show that for SOME infinite
sums, the order you take the terms can make a difference, dispite it
seeming contrary to the nature of addition (infinities break a lot of
common sense).

A key point about your 'static' variable problem. If H really WAS a real
simulator, then there is no issue with the static variable as only one
copy of H is actually execution, all the other copies are just
simulation, so the one variable holding the execution trace hold the
execution trace of the simulation that it is doing, and there is no issue.

The only way that the issue you describe becomes a real issue is if H
doesn't ACTUALLY simulate/debug step through copies of itself, but
applies some sort of 'transform' to the execution, and you need to have
some very good proof that this transform is actually valid, and that the
resulting H, which passes data to embedded copies of itself, and thus
knows of stuff of its environment beyond what it is supposed to know is
actually the equivalent of the decider that doesn't do any of that
'illegal' operations. My guess is that your H is actually NOT the
equivalent of such an actual computation and does actually behave
differently depending on execution environment, and thus fails to meet
the basic requirements.

Remember, if the H inside H^ doesn't behave exactly identical to the H
that is deciding on that H^, then you aren't working on the right
definitions of the system.

This seems to be one of your fundamental tripping point, and is one of
the issues with doing proofs like this in non-Turing Machine environment
(like C/x86 or even RASP) that 'code fragments' can be non-computations
and thus not the equivalent of a Turing Machine.

Re: Why do theory of computation problems require pure functions?

<j8adnV6gzfcKYdj8nZ2dnUU7-V3NnZ2d@giganews.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=21277&group=comp.theory#21277

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!paganini.bofh.team!news.dns-netz.com!news.freedyn.net!newsfeed.xs4all.nl!newsfeed9.news.xs4all.nl!tr1.eu1.usenetexpress.com!feeder.usenetexpress.com!tr3.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sat, 18 Sep 2021 09:49:59 -0500
Subject: Re: Why do theory of computation problems require pure functions?
Newsgroups: comp.theory
References: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com> <si3r5q$8ln$1@dont-email.me> <KZSdncvVqtDkctj8nZ2dnUU7-f_NnZ2d@giganews.com> <ZVm1J.3937$7U3.2717@fx24.iad>
From: NoO...@NoWhere.com (olcott)
Date: Sat, 18 Sep 2021 09:49:58 -0500
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.14.0
MIME-Version: 1.0
In-Reply-To: <ZVm1J.3937$7U3.2717@fx24.iad>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <j8adnV6gzfcKYdj8nZ2dnUU7-V3NnZ2d@giganews.com>
Lines: 122
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-gFDZW/Ujl7b92aY8kvJ+N7bwO3P/ka3dy2jNn3/4bQqIk/Kh0d4A8utLi6PH+oq9Eexyh5yYGwZmL6I!im9404D5kSwLARDnWK2LjJV4DyCflWCplS+/K6krQYduleFhH6gf6WtdBhXAubGgZWz73qxsPTYB!YHM=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 7056
 by: olcott - Sat, 18 Sep 2021 14:49 UTC

On 9/18/2021 9:43 AM, Richard Damon wrote:
>
> On 9/18/21 9:54 AM, olcott wrote:
>> On 9/17/2021 11:50 PM, André G. Isaak wrote:
>>> On 2021-09-17 20:40, olcott wrote:
>>>> Why do theory of computation problems require pure functions?
>>>
>>> Because the theory of computation isn't about C or x86. It isn't about
>>> computer programs at all, nor about modern computers. Just because
>>> 'computation' and 'computer' share the same root doesn't mean they
>>> deal with the same set of phenomena. Remember that the theory of
>>> computation developed before there even were digital computers or
>>> programming languages.
>>>
>>> Computational theory is concerned with describing *mathematical*
>>> functions, and all mathematical functions are pure functions. A
>>> computation is a method for determining the value of the mathematical
>>> function f(x) for a given x. A computable function is one for which it
>>> is possible to construct a TM which, given an input string
>>> representing x, will determine the value of f(x).
>>>
>>> You can write computer programs which perform computations, but the
>>> majority of computer programs don't.
>>>
>>> If you really want to learn about the theory of computation, I'd
>>> suggest that you forget about C or x86 assembly or any sort of
>>> computer language altogether and focus on Turing Machines.
>>>
>>> And don't try to mentally translate anything you read about Turing
>>> Machines into computer languages. Don't think about loop counters, or
>>> calls, or machine addresses, because all of these things pertain to
>>> computers and computer programming rather than computations and they
>>> will get in the way of you actually understanding either turing
>>> machines or the theory of computation more generally.
>>>
>>> André
>>>
>>
>> I only need to know this for one reason.
>>
>> When my halt decider is examining the behavior of its input and the
>> input calls this halt decider in infinite recursion it cannot keep track
>> of the behavior of this input without having a single pseudo static
>> variable that is directly embedded in its machine code.
>>
>> This pseudo static variable stores the ongoing execution trace. When the
>> variable is an ordinary local variable it loses all of its data between
>> each recursive simulation.
>>
>> It still seems to be a pure function of its input in that
>> (1) The function return values are identical for identical arguments
>>
>
> I think the key issue is that if you want to talk about the plain
> behavior of C / x86 code, then you need to talk about the ACTUAL
> behavior of that code, which means that the call to H within the
> simulated machine needs to be seen as a call to H, and NOT some logical
> transformation.
>
> If you want to do the transformation, your need to actually PROVE that
> this transform is legitimate under the conditions you want to make it,
> and that needs a very FORMAL argument based on accepted truths and
> principles. Your 'argument' based on H not affecting P until after it
> makes its decision so it can ignore its effect, is one of those
> arguments that just seems 'obvious' but you haven't actually proved it.
> You don't seem to uhderstand that nature of how to prove something like
> this.
>
> 'Obvious' things can be wrong, like it seems obvious that the order you
> add up a series shouldn't affect the result, even if the number of terms
> in infinite, but there are simple proofs to show that for SOME infinite
> sums, the order you take the terms can make a difference, dispite it
> seeming contrary to the nature of addition (infinities break a lot of
> common sense).
>
>
> A key point about your 'static' variable problem.

There is only a single question here, not the myriad of questions that
you refer to.

Does my use of a single static variable that holds the ongoing execution
trace by itself necessarily completely disqualify my system from
applying to the halting problem or not?

a) Yes
b) No

> If H really WAS a real
> simulator, then there is no issue with the static variable as only one
> copy of H is actually execution, all the other copies are just
> simulation, so the one variable holding the execution trace hold the
> execution trace of the simulation that it is doing, and there is no issue.
>
> The only way that the issue you describe becomes a real issue is if H
> doesn't ACTUALLY simulate/debug step through copies of itself, but
> applies some sort of 'transform' to the execution, and you need to have
> some very good proof that this transform is actually valid, and that the
> resulting H, which passes data to embedded copies of itself, and thus
> knows of stuff of its environment beyond what it is supposed to know is
> actually the equivalent of the decider that doesn't do any of that
> 'illegal' operations. My guess is that your H is actually NOT the
> equivalent of such an actual computation and does actually behave
> differently depending on execution environment, and thus fails to meet
> the basic requirements.
>
> Remember, if the H inside H^ doesn't behave exactly identical to the H
> that is deciding on that H^, then you aren't working on the right
> definitions of the system.
>
> This seems to be one of your fundamental tripping point, and is one of
> the issues with doing proofs like this in non-Turing Machine environment
> (like C/x86 or even RASP) that 'code fragments' can be non-computations
> and thus not the equivalent of a Turing Machine.
>

--
Copyright 2021 Pete Olcott

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

Re: Why do theory of computation problems require pure functions?

<T3n1J.168983$T_8.63230@fx48.iad>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=21278&group=comp.theory#21278

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!aioe.org!news.uzoreto.com!news-out.netnews.com!news.alt.net!fdc2.netnews.com!peer02.ams1!peer.ams1.xlned.com!news.xlned.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!fx48.iad.POSTED!not-for-mail
Subject: Re: Why do theory of computation problems require pure functions?
Newsgroups: comp.theory
References: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>
<si4khe$1nvt$1@gioia.aioe.org>
<mJmdnfaWlv7Kbdj8nZ2dnUU7-YHNnZ2d@giganews.com>
From: Rich...@Damon-Family.org (Richard Damon)
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:78.0)
Gecko/20100101 Thunderbird/78.14.0
MIME-Version: 1.0
In-Reply-To: <mJmdnfaWlv7Kbdj8nZ2dnUU7-YHNnZ2d@giganews.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Lines: 31
Message-ID: <T3n1J.168983$T_8.63230@fx48.iad>
X-Complaints-To: abuse@easynews.com
Organization: Forte - www.forteinc.com
X-Complaints-Info: Please be sure to forward a copy of ALL headers otherwise we will be unable to process your complaint properly.
Date: Sat, 18 Sep 2021 10:53:38 -0400
X-Received-Bytes: 2546
 by: Richard Damon - Sat, 18 Sep 2021 14:53 UTC

On 9/18/21 9:57 AM, olcott wrote:
> On 9/18/2021 7:02 AM, Andy Walker wrote:

>>      Incidentally, please, pretty please, forget about 386
>> machine code.  It really, really doesn't help.  It just obscures
>> whatever argument you're trying to make.  Indeed, it gives the
>> impression that obscurity is what you want [which may, of course,
>> be the case, but if so then stop wasting everyone's time].
>>
>
> I either must stick with C/x86 code or write a RASP machine, the only
> way that my key insights can possible be fully understood is to have
> every single detail as fully operational code such that we can simply
> see what it does and thus not merely imagine what it would do.
>

Note, your traces have exactly the same problem, because you skip over
the tracing of the embedded H with a specious claim that we can ignore
that behavior and replace the simulation of the simulator with a
simulation of the machine that it was simulating.

It is just as possible to provide a full trace of the execution of a
Turing Machine. yes, the trace gets longer, so there is more to wade
through, but it gets around the problem that you actually need to prove
that your C/x86 or RASP code is a Computation.

I think that is the issue, because it appears that it is not, that you
have assumed you H can do things that are NOT possible to actually
implement as an actual Turing Machine of the form claimed, and you need
to stick with those because you can't handle that problem.

Re: Why do theory of computation problems require pure functions?

<si4v0f$u4l$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=21279&group=comp.theory#21279

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: agis...@gm.invalid (André G. Isaak)
Newsgroups: comp.theory
Subject: Re: Why do theory of computation problems require pure functions?
Date: Sat, 18 Sep 2021 09:01:33 -0600
Organization: Christians and Atheists United Against Creeping Agnosticism
Lines: 69
Message-ID: <si4v0f$u4l$1@dont-email.me>
References: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>
<si3r5q$8ln$1@dont-email.me> <KZSdncvVqtDkctj8nZ2dnUU7-f_NnZ2d@giganews.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 18 Sep 2021 15:01:35 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="b2780b02a2648bf8f0dad6d21eb6aca0";
logging-data="30869"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19Xbh/eDGLMXIJsJHidJldo"
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:68.0)
Gecko/20100101 Thunderbird/68.12.1
Cancel-Lock: sha1:AdwuOhW4Ph5jLUOmlrq9DaI6K3o=
In-Reply-To: <KZSdncvVqtDkctj8nZ2dnUU7-f_NnZ2d@giganews.com>
Content-Language: en-US
 by: André G. Isaak - Sat, 18 Sep 2021 15:01 UTC

On 2021-09-18 07:54, olcott wrote:
> On 9/17/2021 11:50 PM, André G. Isaak wrote:
>> On 2021-09-17 20:40, olcott wrote:
>>> Why do theory of computation problems require pure functions?
>>
>> Because the theory of computation isn't about C or x86. It isn't about
>> computer programs at all, nor about modern computers. Just because
>> 'computation' and 'computer' share the same root doesn't mean they
>> deal with the same set of phenomena. Remember that the theory of
>> computation developed before there even were digital computers or
>> programming languages.
>>
>> Computational theory is concerned with describing *mathematical*
>> functions, and all mathematical functions are pure functions. A
>> computation is a method for determining the value of the mathematical
>> function f(x) for a given x. A computable function is one for which it
>> is possible to construct a TM which, given an input string
>> representing x, will determine the value of f(x).
>>
>> You can write computer programs which perform computations, but the
>> majority of computer programs don't.
>>
>> If you really want to learn about the theory of computation, I'd
>> suggest that you forget about C or x86 assembly or any sort of
>> computer language altogether and focus on Turing Machines.
>>
>> And don't try to mentally translate anything you read about Turing
>> Machines into computer languages. Don't think about loop counters, or
>> calls, or machine addresses, because all of these things pertain to
>> computers and computer programming rather than computations and they
>> will get in the way of you actually understanding either turing
>> machines or the theory of computation more generally.
>>
>> André
>>
>
> I only need to know this for one reason.

That's a very odd statement to make. Since you purport to have
'overturned' a significant result in computational theory, I would think
you would want to have a *thorough* understanding of all of the above issues

> When my halt decider is examining the behavior of its input and the
> input calls this halt decider in infinite recursion it cannot keep track
> of the behavior of this input without having a single pseudo static
> variable that is directly embedded in its machine code.

I have no idea what a 'pseudo static variable' is.

> This pseudo static variable stores the ongoing execution trace. When the
> variable is an ordinary local variable it loses all of its data between
> each recursive simulation.
>
> It still seems to be a pure function of its input in that
> (1) The function return values are identical for identical arguments

Except that it doesn't.

According to you P(P) when run from main halts, and thus returns a
value, whereas P(P), when simulated within H doesn't halt, and thus does
not return a value. Returning a value in one case and not returning a
value in another hardly qualifies as "identical [return values] for
identical arguments"

André

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

Re: Why do theory of computation problems require pure functions?

<si4v1h$u4l$2@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=21280&group=comp.theory#21280

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: agis...@gm.invalid (André G. Isaak)
Newsgroups: comp.theory
Subject: Re: Why do theory of computation problems require pure functions?
Date: Sat, 18 Sep 2021 09:02:09 -0600
Organization: Christians and Atheists United Against Creeping Agnosticism
Lines: 17
Message-ID: <si4v1h$u4l$2@dont-email.me>
References: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>
<si3r5q$8ln$1@dont-email.me> <KZSdncvVqtDkctj8nZ2dnUU7-f_NnZ2d@giganews.com>
<ZVm1J.3937$7U3.2717@fx24.iad>
<j8adnV6gzfcKYdj8nZ2dnUU7-V3NnZ2d@giganews.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 18 Sep 2021 15:02:09 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="b2780b02a2648bf8f0dad6d21eb6aca0";
logging-data="30869"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX18lEakuvHsqNwOY5/TqrsNv"
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:68.0)
Gecko/20100101 Thunderbird/68.12.1
Cancel-Lock: sha1:WgmOvdtYNc4WAPDJOWnHOAu62u8=
In-Reply-To: <j8adnV6gzfcKYdj8nZ2dnUU7-V3NnZ2d@giganews.com>
Content-Language: en-US
 by: André G. Isaak - Sat, 18 Sep 2021 15:02 UTC

On 2021-09-18 08:49, olcott wrote:
> On 9/18/2021 9:43 AM, Richard Damon wrote:

> Does my use of a single static variable that holds the ongoing execution
> trace by itself necessarily completely disqualify my system from
> applying to the halting problem or not?
>
> a) Yes
> b) No

(a) Yes.

André

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

Re: Why do theory of computation problems require pure functions?

<si4v6h$u4l$3@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=21281&group=comp.theory#21281

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: agis...@gm.invalid (André G. Isaak)
Newsgroups: comp.theory
Subject: Re: Why do theory of computation problems require pure functions?
Date: Sat, 18 Sep 2021 09:04:49 -0600
Organization: Christians and Atheists United Against Creeping Agnosticism
Lines: 17
Message-ID: <si4v6h$u4l$3@dont-email.me>
References: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>
<si4khe$1nvt$1@gioia.aioe.org>
<mJmdnfaWlv7Kbdj8nZ2dnUU7-YHNnZ2d@giganews.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 18 Sep 2021 15:04:49 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="b2780b02a2648bf8f0dad6d21eb6aca0";
logging-data="30869"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+LLmidpmom/kcrQ9xQKiQi"
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.14; rv:68.0)
Gecko/20100101 Thunderbird/68.12.1
Cancel-Lock: sha1:BB5u16xQMPqo5NgYxgtDotvRRU4=
In-Reply-To: <mJmdnfaWlv7Kbdj8nZ2dnUU7-YHNnZ2d@giganews.com>
Content-Language: en-US
 by: André G. Isaak - Sat, 18 Sep 2021 15:04 UTC

On 2021-09-18 07:57, olcott wrote:

> I either must stick with C/x86 code or write a RASP machine, the only
> way that my key insights can possible be fully understood is to have
> every single detail as fully operational code such that we can simply
> see what it does and thus not merely imagine what it would do.

Why do you insist on continuously repeating this rather ridiculous claim?

When working with Turing Machines one doesn't need to 'merely imagine
what it would do.' One can see *exactly* what it does.

André

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

Re: Why do theory of computation problems require pure functions?

<XMWdnTGSKtQenNv8nZ2dnUU7-LPNnZ2d@giganews.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=21282&group=comp.theory#21282

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sat, 18 Sep 2021 10:10:59 -0500
Subject: Re: Why do theory of computation problems require pure functions?
Newsgroups: comp.theory
References: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>
<si3r5q$8ln$1@dont-email.me> <KZSdncvVqtDkctj8nZ2dnUU7-f_NnZ2d@giganews.com>
<si4v0f$u4l$1@dont-email.me>
From: NoO...@NoWhere.com (olcott)
Date: Sat, 18 Sep 2021 10:10:58 -0500
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.14.0
MIME-Version: 1.0
In-Reply-To: <si4v0f$u4l$1@dont-email.me>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <XMWdnTGSKtQenNv8nZ2dnUU7-LPNnZ2d@giganews.com>
Lines: 95
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-IJ6J/PcvCKE1Y5H+0yKxFKi9i0PNLbQX6z0snoMtIdPPIg16QjKmQE4zoK2ov+SXxJIxAIzk/SiJ+/J!k2iZIH+Zih1j74EehZdLZmt4+wO8A0JBbu126EL6BT1YOhEJpg/HxhJLsqmGzlnlbRL6C9GJ6mu5!204=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 5280
 by: olcott - Sat, 18 Sep 2021 15:10 UTC

On 9/18/2021 10:01 AM, André G. Isaak wrote:
> On 2021-09-18 07:54, olcott wrote:
>> On 9/17/2021 11:50 PM, André G. Isaak wrote:
>>> On 2021-09-17 20:40, olcott wrote:
>>>> Why do theory of computation problems require pure functions?
>>>
>>> Because the theory of computation isn't about C or x86. It isn't
>>> about computer programs at all, nor about modern computers. Just
>>> because 'computation' and 'computer' share the same root doesn't mean
>>> they deal with the same set of phenomena. Remember that the theory of
>>> computation developed before there even were digital computers or
>>> programming languages.
>>>
>>> Computational theory is concerned with describing *mathematical*
>>> functions, and all mathematical functions are pure functions. A
>>> computation is a method for determining the value of the mathematical
>>> function f(x) for a given x. A computable function is one for which
>>> it is possible to construct a TM which, given an input string
>>> representing x, will determine the value of f(x).
>>>
>>> You can write computer programs which perform computations, but the
>>> majority of computer programs don't.
>>>
>>> If you really want to learn about the theory of computation, I'd
>>> suggest that you forget about C or x86 assembly or any sort of
>>> computer language altogether and focus on Turing Machines.
>>>
>>> And don't try to mentally translate anything you read about Turing
>>> Machines into computer languages. Don't think about loop counters, or
>>> calls, or machine addresses, because all of these things pertain to
>>> computers and computer programming rather than computations and they
>>> will get in the way of you actually understanding either turing
>>> machines or the theory of computation more generally.
>>>
>>> André
>>>
>>
>> I only need to know this for one reason.
>
> That's a very odd statement to make. Since you purport to have
> 'overturned' a significant result in computational theory, I would think
> you would want to have a *thorough* understanding of all of the above
> issues
>

Anything that does not directly apply to my work is moot.

>> When my halt decider is examining the behavior of its input and the
>> input calls this halt decider in infinite recursion it cannot keep
>> track of the behavior of this input without having a single pseudo
>> static variable that is directly embedded in its machine code.
>
> I have no idea what a 'pseudo static variable' is.

Instead of simply declaring the variable as static where the compiler
places it in global data I directly embed the variable in the function's
machine code.

>
>> This pseudo static variable stores the ongoing execution trace. When
>> the variable is an ordinary local variable it loses all of its data
>> between each recursive simulation.
>>
>> It still seems to be a pure function of its input in that
>> (1) The function return values are identical for identical arguments
>
> Except that it doesn't.
>

For the purpose of this dialogue it is stipulated that it does, thus
even if it does not it is to be construed that it does.

If we assume that all cats are dogs then the question:
Do cats bark is correctly anwered as: yes.

> According to you P(P) when run from main halts, and thus returns a
> value, whereas P(P), when simulated within H doesn't halt, and thus does
> not return a value. Returning a value in one case and not returning a
> value in another hardly qualifies as "identical [return values] for
> identical arguments"
>
> André
>

I am not going to get into your lack of comprehension of this.

I merely need to know, does my use of a static variable by-itself make
my system no longer apply to the halting problem?

--
Copyright 2021 Pete Olcott

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

Re: Why do theory of computation problems require pure functions?

<lmn1J.84222$jl2.75920@fx34.iad>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=21283&group=comp.theory#21283

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!fx34.iad.POSTED!not-for-mail
Subject: Re: Why do theory of computation problems require pure functions?
Newsgroups: comp.theory
References: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>
<si3r5q$8ln$1@dont-email.me> <KZSdncvVqtDkctj8nZ2dnUU7-f_NnZ2d@giganews.com>
<ZVm1J.3937$7U3.2717@fx24.iad>
<j8adnV6gzfcKYdj8nZ2dnUU7-V3NnZ2d@giganews.com>
From: Rich...@Damon-Family.org (Richard Damon)
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:78.0)
Gecko/20100101 Thunderbird/78.14.0
MIME-Version: 1.0
In-Reply-To: <j8adnV6gzfcKYdj8nZ2dnUU7-V3NnZ2d@giganews.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Lines: 145
Message-ID: <lmn1J.84222$jl2.75920@fx34.iad>
X-Complaints-To: abuse@easynews.com
Organization: Forte - www.forteinc.com
X-Complaints-Info: Please be sure to forward a copy of ALL headers otherwise we will be unable to process your complaint properly.
Date: Sat, 18 Sep 2021 11:13:20 -0400
X-Received-Bytes: 8098
X-Original-Bytes: 7965
 by: Richard Damon - Sat, 18 Sep 2021 15:13 UTC

On 9/18/21 10:49 AM, olcott wrote:
> On 9/18/2021 9:43 AM, Richard Damon wrote:
>>
>> On 9/18/21 9:54 AM, olcott wrote:
>>> On 9/17/2021 11:50 PM, André G. Isaak wrote:
>>>> On 2021-09-17 20:40, olcott wrote:
>>>>> Why do theory of computation problems require pure functions?
>>>>
>>>> Because the theory of computation isn't about C or x86. It isn't about
>>>> computer programs at all, nor about modern computers. Just because
>>>> 'computation' and 'computer' share the same root doesn't mean they
>>>> deal with the same set of phenomena. Remember that the theory of
>>>> computation developed before there even were digital computers or
>>>> programming languages.
>>>>
>>>> Computational theory is concerned with describing *mathematical*
>>>> functions, and all mathematical functions are pure functions. A
>>>> computation is a method for determining the value of the mathematical
>>>> function f(x) for a given x. A computable function is one for which it
>>>> is possible to construct a TM which, given an input string
>>>> representing x, will determine the value of f(x).
>>>>
>>>> You can write computer programs which perform computations, but the
>>>> majority of computer programs don't.
>>>>
>>>> If you really want to learn about the theory of computation, I'd
>>>> suggest that you forget about C or x86 assembly or any sort of
>>>> computer language altogether and focus on Turing Machines.
>>>>
>>>> And don't try to mentally translate anything you read about Turing
>>>> Machines into computer languages. Don't think about loop counters, or
>>>> calls, or machine addresses, because all of these things pertain to
>>>> computers and computer programming rather than computations and they
>>>> will get in the way of you actually understanding either turing
>>>> machines or the theory of computation more generally.
>>>>
>>>> André
>>>>
>>>
>>> I only need to know this for one reason.
>>>
>>> When my halt decider is examining the behavior of its input and the
>>> input calls this halt decider in infinite recursion it cannot keep track
>>> of the behavior of this input without having a single pseudo static
>>> variable that is directly embedded in its machine code.
>>>
>>> This pseudo static variable stores the ongoing execution trace. When the
>>> variable is an ordinary local variable it loses all of its data between
>>> each recursive simulation.
>>>
>>> It still seems to be a pure function of its input in that
>>> (1) The function return values are identical for identical arguments
>>>
>>
>> I think the key issue is that if you want to talk about the plain
>> behavior of C / x86 code, then you need to talk about the ACTUAL
>> behavior of that code, which means that the call to H within the
>> simulated machine needs to be seen as a call to H, and NOT some logical
>> transformation.
>>
>> If you want to do the transformation, your need to actually PROVE that
>> this transform is legitimate under the conditions you want to make it,
>> and that needs a very FORMAL argument based on accepted truths and
>> principles. Your 'argument' based on H not affecting P until after it
>> makes its decision so it can ignore its effect, is one of those
>> arguments that just seems 'obvious' but you haven't actually proved it.
>> You don't seem to uhderstand that nature of how to prove something like
>> this.
>>
>> 'Obvious' things can be wrong, like it seems obvious that the order you
>> add up a series shouldn't affect the result, even if the number of terms
>> in infinite, but there are simple proofs to show that for SOME infinite
>> sums, the order you take the terms can make a difference, dispite it
>> seeming contrary to the nature of addition (infinities break a lot of
>> common sense).
>>
>>
>> A key point about your 'static' variable problem.
>
> There is only a single question here, not the myriad of questions that
> you refer to.
>
> Does my use of a single static variable that holds the ongoing execution
> trace by itself necessarily completely disqualify my system from
> applying to the halting problem or not?
>
> a) Yes
> b) No

Error of the Complex Question, just like the question of "Have you
stopped lying about your Halt Decider?".

It isn't the existence of a static variable itself that might disqualify
your system for applying to the halting problem, but does the existence
of that variable, and the way that your program uses it mean that H is
not an actual Computation. The existence of the variable opens the door
to it being disqualified, but the actual disqualification needs more
information.

If EVERY call to H(P,I) for a given P and I returns the exact same
answer every time, then H is still a computation.

The key point here is that When H decides on the call H(P,P) and in that
simulation of P(P) there is a call to H(P,P) then the 'correct' answer
for H needs to take into account that this simulated WILL do exactly the
same thing as the H that is doing the simulation, so if the simulating H
is going to answer Non-Halting, the behavior of the simulated machine
will be based on that simulated H also returning that same answer. Yes,
H is not going to have simulated to that point of the simulated machines
execution, so the simulating H will not be able to see that result, but
that IS the behavior of the machine that it is simulating, and thus
affect what is the 'Right' answer for H to give.

>
>> If H really WAS a real
>> simulator, then there is no issue with the static variable as only one
>> copy of H is actually execution, all the other copies are just
>> simulation, so the one variable holding the execution trace hold the
>> execution trace of the simulation that it is doing, and there is no
>> issue.
>>
>> The only way that the issue you describe becomes a real issue is if H
>> doesn't ACTUALLY simulate/debug step through copies of itself, but
>> applies some sort of 'transform' to the execution, and you need to have
>> some very good proof that this transform is actually valid, and that the
>> resulting H, which passes data to embedded copies of itself, and thus
>> knows of stuff of its environment beyond what it is supposed to know is
>> actually the equivalent of the decider that doesn't do any of that
>> 'illegal' operations. My guess is that your H is actually NOT the
>> equivalent of such an actual computation and does actually behave
>> differently depending on execution environment, and thus fails to meet
>> the basic requirements.
>>
>> Remember, if the H inside H^ doesn't behave exactly identical to the H
>> that is deciding on that H^, then you aren't working on the right
>> definitions of the system.
>>
>> This seems to be one of your fundamental tripping point, and is one of
>> the issues with doing proofs like this in non-Turing Machine environment
>> (like C/x86 or even RASP) that 'code fragments' can be non-computations
>> and thus not the equivalent of a Turing Machine.
>>
>
>

Re: Why do theory of computation problems require pure functions?

<XMWdnTCSKtSKn9v8nZ2dnUU7-LOdnZ2d@giganews.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=21284&group=comp.theory#21284

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sat, 18 Sep 2021 10:13:26 -0500
Subject: Re: Why do theory of computation problems require pure functions?
Newsgroups: comp.theory
References: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>
<si3r5q$8ln$1@dont-email.me> <KZSdncvVqtDkctj8nZ2dnUU7-f_NnZ2d@giganews.com>
<ZVm1J.3937$7U3.2717@fx24.iad>
<j8adnV6gzfcKYdj8nZ2dnUU7-V3NnZ2d@giganews.com> <si4v1h$u4l$2@dont-email.me>
From: NoO...@NoWhere.com (olcott)
Date: Sat, 18 Sep 2021 10:13:25 -0500
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.14.0
MIME-Version: 1.0
In-Reply-To: <si4v1h$u4l$2@dont-email.me>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <XMWdnTCSKtSKn9v8nZ2dnUU7-LOdnZ2d@giganews.com>
Lines: 25
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-79NzYGRtgHXRBm+1Uc5gppSHWCKK7tIx6DEOj3wMPhtM4JdcQI0MAFGmnctbNUWOiH1EnXc9uEjUqYP!IRZb94Xud+XrAAQNuLGaWcIEA2+mOaDGQQUGaK9vDJwTfU72QxWNkEj+nQIIni5YlI0KB/ibPR1C!9Zo=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 2125
 by: olcott - Sat, 18 Sep 2021 15:13 UTC

On 9/18/2021 10:02 AM, André G. Isaak wrote:
> On 2021-09-18 08:49, olcott wrote:
>> On 9/18/2021 9:43 AM, Richard Damon wrote:
>
>> Does my use of a single static variable that holds the ongoing
>> execution trace by itself necessarily completely disqualify my system
>> from applying to the halting problem or not?
>>
>> a) Yes
>> b) No
>
> (a) Yes.
>
> André
>

What difference does it make in terms of deriving the correct halt
status? It can be empirically verified that the halt status is correct,
thus the "pure function" requirement seems to be arbitrary.

--
Copyright 2021 Pete Olcott

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

Re: Why do theory of computation problems require pure functions?

<Nc6dnYeBOsuRntv8nZ2dnUU7-QfNnZ2d@giganews.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=21285&group=comp.theory#21285

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!aioe.org!feeder1.feed.usenet.farm!feed.usenet.farm!tr3.eu1.usenetexpress.com!feeder.usenetexpress.com!tr1.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sat, 18 Sep 2021 10:17:32 -0500
Subject: Re: Why do theory of computation problems require pure functions?
Newsgroups: comp.theory
References: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com> <si4khe$1nvt$1@gioia.aioe.org> <mJmdnfaWlv7Kbdj8nZ2dnUU7-YHNnZ2d@giganews.com> <si4v6h$u4l$3@dont-email.me>
From: NoO...@NoWhere.com (olcott)
Date: Sat, 18 Sep 2021 10:17:30 -0500
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101 Thunderbird/78.14.0
MIME-Version: 1.0
In-Reply-To: <si4v6h$u4l$3@dont-email.me>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <Nc6dnYeBOsuRntv8nZ2dnUU7-QfNnZ2d@giganews.com>
Lines: 26
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-fe3do2ChkgjHaW7LXS5ZMrBe6dsCVP52/9ZqVVjknTB459VlkM0SOrus3jDsByQyrRX5BNVRVneY5Vc!FNHSPQVVdpa98wpLzlaxVoI0H2/pnQmlrL3ZjFKXlNXvEHxzOxFZ6m2EaBDyE3N4t6QrItjehCzw!tTY=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 2247
 by: olcott - Sat, 18 Sep 2021 15:17 UTC

On 9/18/2021 10:04 AM, André G. Isaak wrote:
> On 2021-09-18 07:57, olcott wrote:
>
>> I either must stick with C/x86 code or write a RASP machine, the only
>> way that my key insights can possible be fully understood is to have
>> every single detail as fully operational code such that we can simply
>> see what it does and thus not merely imagine what it would do.
>
> Why do you insist on continuously repeating this rather ridiculous claim?
>
> When working with Turing Machines one doesn't need to 'merely imagine
> what it would do.' One can see *exactly* what it does.
>
> André
>

When H is defined as a simulating halt decider then H correctly decides
the halt status of ⟨Ĥ⟩ ⟨Ĥ⟩.

https://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf

--
Copyright 2021 Pete Olcott

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

Re: Why do theory of computation problems require pure functions?

<Nc6dnYaBOsvxntv8nZ2dnUU7-QednZ2d@giganews.com>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=21286&group=comp.theory#21286

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!buffer2.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Sat, 18 Sep 2021 10:19:08 -0500
Subject: Re: Why do theory of computation problems require pure functions?
Newsgroups: comp.theory
References: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>
<si3r5q$8ln$1@dont-email.me> <KZSdncvVqtDkctj8nZ2dnUU7-f_NnZ2d@giganews.com>
<ZVm1J.3937$7U3.2717@fx24.iad>
<j8adnV6gzfcKYdj8nZ2dnUU7-V3NnZ2d@giganews.com>
<lmn1J.84222$jl2.75920@fx34.iad>
From: NoO...@NoWhere.com (olcott)
Date: Sat, 18 Sep 2021 10:19:07 -0500
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.14.0
MIME-Version: 1.0
In-Reply-To: <lmn1J.84222$jl2.75920@fx34.iad>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Message-ID: <Nc6dnYaBOsvxntv8nZ2dnUU7-QednZ2d@giganews.com>
Lines: 157
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-ysx+WW/6CUdouVpDULebfQvdJAkGAupfHgkhOS6orXogDSkfFD4p73Y1I1x3DHzpUO8LDrzKj07O9oM!Tpd0aZN+3H/LxlbkCOuDhkHr1ax5sc8svBX/q9dRAH+5JjP+2KqyhxiaTEi/kuiU4Pd6x8dfmc8C!yeE=
X-Complaints-To: abuse@giganews.com
X-DMCA-Notifications: http://www.giganews.com/info/dmca.html
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40
X-Original-Bytes: 8891
 by: olcott - Sat, 18 Sep 2021 15:19 UTC

On 9/18/2021 10:13 AM, Richard Damon wrote:
> On 9/18/21 10:49 AM, olcott wrote:
>> On 9/18/2021 9:43 AM, Richard Damon wrote:
>>>
>>> On 9/18/21 9:54 AM, olcott wrote:
>>>> On 9/17/2021 11:50 PM, André G. Isaak wrote:
>>>>> On 2021-09-17 20:40, olcott wrote:
>>>>>> Why do theory of computation problems require pure functions?
>>>>>
>>>>> Because the theory of computation isn't about C or x86. It isn't about
>>>>> computer programs at all, nor about modern computers. Just because
>>>>> 'computation' and 'computer' share the same root doesn't mean they
>>>>> deal with the same set of phenomena. Remember that the theory of
>>>>> computation developed before there even were digital computers or
>>>>> programming languages.
>>>>>
>>>>> Computational theory is concerned with describing *mathematical*
>>>>> functions, and all mathematical functions are pure functions. A
>>>>> computation is a method for determining the value of the mathematical
>>>>> function f(x) for a given x. A computable function is one for which it
>>>>> is possible to construct a TM which, given an input string
>>>>> representing x, will determine the value of f(x).
>>>>>
>>>>> You can write computer programs which perform computations, but the
>>>>> majority of computer programs don't.
>>>>>
>>>>> If you really want to learn about the theory of computation, I'd
>>>>> suggest that you forget about C or x86 assembly or any sort of
>>>>> computer language altogether and focus on Turing Machines.
>>>>>
>>>>> And don't try to mentally translate anything you read about Turing
>>>>> Machines into computer languages. Don't think about loop counters, or
>>>>> calls, or machine addresses, because all of these things pertain to
>>>>> computers and computer programming rather than computations and they
>>>>> will get in the way of you actually understanding either turing
>>>>> machines or the theory of computation more generally.
>>>>>
>>>>> André
>>>>>
>>>>
>>>> I only need to know this for one reason.
>>>>
>>>> When my halt decider is examining the behavior of its input and the
>>>> input calls this halt decider in infinite recursion it cannot keep track
>>>> of the behavior of this input without having a single pseudo static
>>>> variable that is directly embedded in its machine code.
>>>>
>>>> This pseudo static variable stores the ongoing execution trace. When the
>>>> variable is an ordinary local variable it loses all of its data between
>>>> each recursive simulation.
>>>>
>>>> It still seems to be a pure function of its input in that
>>>> (1) The function return values are identical for identical arguments
>>>>
>>>
>>> I think the key issue is that if you want to talk about the plain
>>> behavior of C / x86 code, then you need to talk about the ACTUAL
>>> behavior of that code, which means that the call to H within the
>>> simulated machine needs to be seen as a call to H, and NOT some logical
>>> transformation.
>>>
>>> If you want to do the transformation, your need to actually PROVE that
>>> this transform is legitimate under the conditions you want to make it,
>>> and that needs a very FORMAL argument based on accepted truths and
>>> principles. Your 'argument' based on H not affecting P until after it
>>> makes its decision so it can ignore its effect, is one of those
>>> arguments that just seems 'obvious' but you haven't actually proved it.
>>> You don't seem to uhderstand that nature of how to prove something like
>>> this.
>>>
>>> 'Obvious' things can be wrong, like it seems obvious that the order you
>>> add up a series shouldn't affect the result, even if the number of terms
>>> in infinite, but there are simple proofs to show that for SOME infinite
>>> sums, the order you take the terms can make a difference, dispite it
>>> seeming contrary to the nature of addition (infinities break a lot of
>>> common sense).
>>>
>>>
>>> A key point about your 'static' variable problem.
>>
>> There is only a single question here, not the myriad of questions that
>> you refer to.
>>
>> Does my use of a single static variable that holds the ongoing execution
>> trace by itself necessarily completely disqualify my system from
>> applying to the halting problem or not?
>>
>> a) Yes
>> b) No
>
> Error of the Complex Question, just like the question of "Have you
> stopped lying about your Halt Decider?".
>
> It isn't the existence of a static variable itself that might disqualify
> your system for applying to the halting problem,

André disagrees so one of you must be wrong.

> but does the existence
> of that variable, and the way that your program uses it mean that H is
> not an actual Computation. The existence of the variable opens the door
> to it being disqualified, but the actual disqualification needs more
> information.
>
> If EVERY call to H(P,I) for a given P and I returns the exact same
> answer every time, then H is still a computation.
>
> The key point here is that When H decides on the call H(P,P) and in that
> simulation of P(P) there is a call to H(P,P) then the 'correct' answer
> for H needs to take into account that this simulated WILL do exactly the
> same thing as the H that is doing the simulation, so if the simulating H
> is going to answer Non-Halting, the behavior of the simulated machine
> will be based on that simulated H also returning that same answer. Yes,
> H is not going to have simulated to that point of the simulated machines
> execution, so the simulating H will not be able to see that result, but
> that IS the behavior of the machine that it is simulating, and thus
> affect what is the 'Right' answer for H to give.
>
>>
>>> If H really WAS a real
>>> simulator, then there is no issue with the static variable as only one
>>> copy of H is actually execution, all the other copies are just
>>> simulation, so the one variable holding the execution trace hold the
>>> execution trace of the simulation that it is doing, and there is no
>>> issue.
>>>
>>> The only way that the issue you describe becomes a real issue is if H
>>> doesn't ACTUALLY simulate/debug step through copies of itself, but
>>> applies some sort of 'transform' to the execution, and you need to have
>>> some very good proof that this transform is actually valid, and that the
>>> resulting H, which passes data to embedded copies of itself, and thus
>>> knows of stuff of its environment beyond what it is supposed to know is
>>> actually the equivalent of the decider that doesn't do any of that
>>> 'illegal' operations. My guess is that your H is actually NOT the
>>> equivalent of such an actual computation and does actually behave
>>> differently depending on execution environment, and thus fails to meet
>>> the basic requirements.
>>>
>>> Remember, if the H inside H^ doesn't behave exactly identical to the H
>>> that is deciding on that H^, then you aren't working on the right
>>> definitions of the system.
>>>
>>> This seems to be one of your fundamental tripping point, and is one of
>>> the issues with doing proofs like this in non-Turing Machine environment
>>> (like C/x86 or even RASP) that 'code fragments' can be non-computations
>>> and thus not the equivalent of a Turing Machine.
>>>
>>
>>
>

--
Copyright 2021 Pete Olcott

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

Re: Why do theory of computation problems require pure functions?

<rvn1J.130329$o45.114860@fx46.iad>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=21287&group=comp.theory#21287

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!4.us.feeder.erje.net!2.eu.feeder.erje.net!feeder.erje.net!newsreader4.netcologne.de!news.netcologne.de!peer02.ams1!peer.ams1.xlned.com!news.xlned.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!fx46.iad.POSTED!not-for-mail
Subject: Re: Why do theory of computation problems require pure functions?
Newsgroups: comp.theory
References: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>
<si3r5q$8ln$1@dont-email.me> <KZSdncvVqtDkctj8nZ2dnUU7-f_NnZ2d@giganews.com>
<ZVm1J.3937$7U3.2717@fx24.iad>
<j8adnV6gzfcKYdj8nZ2dnUU7-V3NnZ2d@giganews.com> <si4v1h$u4l$2@dont-email.me>
From: Rich...@Damon-Family.org (Richard Damon)
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:78.0)
Gecko/20100101 Thunderbird/78.14.0
MIME-Version: 1.0
In-Reply-To: <si4v1h$u4l$2@dont-email.me>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Lines: 34
Message-ID: <rvn1J.130329$o45.114860@fx46.iad>
X-Complaints-To: abuse@easynews.com
Organization: Forte - www.forteinc.com
X-Complaints-Info: Please be sure to forward a copy of ALL headers otherwise we will be unable to process your complaint properly.
Date: Sat, 18 Sep 2021 11:23:03 -0400
X-Received-Bytes: 2447
 by: Richard Damon - Sat, 18 Sep 2021 15:23 UTC

On 9/18/21 11:02 AM, André G. Isaak wrote:
> On 2021-09-18 08:49, olcott wrote:
>> On 9/18/2021 9:43 AM, Richard Damon wrote:
>
>> Does my use of a single static variable that holds the ongoing
>> execution trace by itself necessarily completely disqualify my system
>> from applying to the halting problem or not?
>>
>> a) Yes
>> b) No
>
> (a) Yes.
>
> André
>

That is incorrect, as it is quite possible to have a program that IS a
computation that still has a static variable, it a categorical No can be
disproven.

If his halt decider does ACTUALLY SIMULATE the provided program (and not
execute it under a debugger) then in the execution context of the
decider never actually has any recursion occurring, so only one copy of
the decider ever sees that value of that variable at any given time.

Yes, it appears that the way his current design works, the static
variable provides an information back channel between different 'levels'
of the decider running and that affects the behavior of the different
'levels' so it is not a Computation, but the mere presence of a static
variable isn't enough.

For example, the common trick of memoizing a function to save previous
calculated results to make it run faster does not in of itself
disqualify a function from being a true computation.

Re: Why do theory of computation problems require pure functions?

<Awn1J.130330$o45.49337@fx46.iad>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=21288&group=comp.theory#21288

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder8.news.weretis.net!npeer.as286.net!npeer-ng0.as286.net!peer02.ams1!peer.ams1.xlned.com!news.xlned.com!peer03.iad!feed-me.highwinds-media.com!news.highwinds-media.com!fx46.iad.POSTED!not-for-mail
Subject: Re: Why do theory of computation problems require pure functions?
Newsgroups: comp.theory
References: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>
<si4khe$1nvt$1@gioia.aioe.org>
<mJmdnfaWlv7Kbdj8nZ2dnUU7-YHNnZ2d@giganews.com> <si4v6h$u4l$3@dont-email.me>
<Nc6dnYeBOsuRntv8nZ2dnUU7-QfNnZ2d@giganews.com>
From: Rich...@Damon-Family.org (Richard Damon)
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:78.0)
Gecko/20100101 Thunderbird/78.14.0
MIME-Version: 1.0
In-Reply-To: <Nc6dnYeBOsuRntv8nZ2dnUU7-QfNnZ2d@giganews.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Lines: 25
Message-ID: <Awn1J.130330$o45.49337@fx46.iad>
X-Complaints-To: abuse@easynews.com
Organization: Forte - www.forteinc.com
X-Complaints-Info: Please be sure to forward a copy of ALL headers otherwise we will be unable to process your complaint properly.
Date: Sat, 18 Sep 2021 11:24:16 -0400
X-Received-Bytes: 2039
 by: Richard Damon - Sat, 18 Sep 2021 15:24 UTC

On 9/18/21 11:17 AM, olcott wrote:
> On 9/18/2021 10:04 AM, André G. Isaak wrote:
>> On 2021-09-18 07:57, olcott wrote:
>>
>>> I either must stick with C/x86 code or write a RASP machine, the only
>>> way that my key insights can possible be fully understood is to have
>>> every single detail as fully operational code such that we can simply
>>> see what it does and thus not merely imagine what it would do.
>>
>> Why do you insist on continuously repeating this rather ridiculous claim?
>>
>> When working with Turing Machines one doesn't need to 'merely imagine
>> what it would do.' One can see *exactly* what it does.
>>
>> André
>>
>
> When H is defined as a simulating halt decider then H correctly decides
> the halt status of ⟨Ĥ⟩ ⟨Ĥ⟩.
>
> https://www.liarparadox.org/Peter_Linz_HP(Pages_315-320).pdf
>

Except that it doesn't, as H says H^(H^) is non-halting when it actually
Halts.

Re: Why do theory of computation problems require pure functions?

<Cxn1J.130331$o45.17922@fx46.iad>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=21289&group=comp.theory#21289

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!nntp.giganews.com!peer02.iad!feed-me.highwinds-media.com!news.highwinds-media.com!fx46.iad.POSTED!not-for-mail
Subject: Re: Why do theory of computation problems require pure functions?
Newsgroups: comp.theory
References: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>
<si3r5q$8ln$1@dont-email.me> <KZSdncvVqtDkctj8nZ2dnUU7-f_NnZ2d@giganews.com>
<ZVm1J.3937$7U3.2717@fx24.iad>
<j8adnV6gzfcKYdj8nZ2dnUU7-V3NnZ2d@giganews.com>
<lmn1J.84222$jl2.75920@fx34.iad>
<Nc6dnYaBOsvxntv8nZ2dnUU7-QednZ2d@giganews.com>
From: Rich...@Damon-Family.org (Richard Damon)
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:78.0)
Gecko/20100101 Thunderbird/78.14.0
MIME-Version: 1.0
In-Reply-To: <Nc6dnYaBOsvxntv8nZ2dnUU7-QednZ2d@giganews.com>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
Lines: 166
Message-ID: <Cxn1J.130331$o45.17922@fx46.iad>
X-Complaints-To: abuse@easynews.com
Organization: Forte - www.forteinc.com
X-Complaints-Info: Please be sure to forward a copy of ALL headers otherwise we will be unable to process your complaint properly.
Date: Sat, 18 Sep 2021 11:25:22 -0400
X-Received-Bytes: 8760
X-Original-Bytes: 8627
 by: Richard Damon - Sat, 18 Sep 2021 15:25 UTC

On 9/18/21 11:19 AM, olcott wrote:
> On 9/18/2021 10:13 AM, Richard Damon wrote:
>> On 9/18/21 10:49 AM, olcott wrote:
>>> On 9/18/2021 9:43 AM, Richard Damon wrote:
>>>>
>>>> On 9/18/21 9:54 AM, olcott wrote:
>>>>> On 9/17/2021 11:50 PM, André G. Isaak wrote:
>>>>>> On 2021-09-17 20:40, olcott wrote:
>>>>>>> Why do theory of computation problems require pure functions?
>>>>>>
>>>>>> Because the theory of computation isn't about C or x86. It isn't
>>>>>> about
>>>>>> computer programs at all, nor about modern computers. Just because
>>>>>> 'computation' and 'computer' share the same root doesn't mean they
>>>>>> deal with the same set of phenomena. Remember that the theory of
>>>>>> computation developed before there even were digital computers or
>>>>>> programming languages.
>>>>>>
>>>>>> Computational theory is concerned with describing *mathematical*
>>>>>> functions, and all mathematical functions are pure functions. A
>>>>>> computation is a method for determining the value of the mathematical
>>>>>> function f(x) for a given x. A computable function is one for
>>>>>> which it
>>>>>> is possible to construct a TM which, given an input string
>>>>>> representing x, will determine the value of f(x).
>>>>>>
>>>>>> You can write computer programs which perform computations, but the
>>>>>> majority of computer programs don't.
>>>>>>
>>>>>> If you really want to learn about the theory of computation, I'd
>>>>>> suggest that you forget about C or x86 assembly or any sort of
>>>>>> computer language altogether and focus on Turing Machines.
>>>>>>
>>>>>> And don't try to mentally translate anything you read about Turing
>>>>>> Machines into computer languages. Don't think about loop counters, or
>>>>>> calls, or machine addresses, because all of these things pertain to
>>>>>> computers and computer programming rather than computations and they
>>>>>> will get in the way of you actually understanding either turing
>>>>>> machines or the theory of computation more generally.
>>>>>>
>>>>>> André
>>>>>>
>>>>>
>>>>> I only need to know this for one reason.
>>>>>
>>>>> When my halt decider is examining the behavior of its input and the
>>>>> input calls this halt decider in infinite recursion it cannot keep
>>>>> track
>>>>> of the behavior of this input without having a single pseudo static
>>>>> variable that is directly embedded in its machine code.
>>>>>
>>>>> This pseudo static variable stores the ongoing execution trace.
>>>>> When the
>>>>> variable is an ordinary local variable it loses all of its data
>>>>> between
>>>>> each recursive simulation.
>>>>>
>>>>> It still seems to be a pure function of its input in that
>>>>> (1) The function return values are identical for identical arguments
>>>>>
>>>>
>>>> I think the key issue is that if you want to talk about the plain
>>>> behavior of C / x86 code, then you need to talk about the ACTUAL
>>>> behavior of that code, which means that the call to H within the
>>>> simulated machine needs to be seen as a call to H, and NOT some logical
>>>> transformation.
>>>>
>>>> If you want to do the transformation, your need to actually PROVE that
>>>> this transform is legitimate under the conditions you want to make it,
>>>> and that needs a very FORMAL argument based on accepted truths and
>>>> principles. Your 'argument' based on H not affecting P until after it
>>>> makes its decision so it can ignore its effect, is one of those
>>>> arguments that just seems 'obvious' but you haven't actually proved it.
>>>> You don't seem to uhderstand that nature of how to prove something like
>>>> this.
>>>>
>>>> 'Obvious' things can be wrong, like it seems obvious that the order you
>>>> add up a series shouldn't affect the result, even if the number of
>>>> terms
>>>> in infinite, but there are simple proofs to show that for SOME infinite
>>>> sums, the order you take the terms can make a difference, dispite it
>>>> seeming contrary to the nature of addition (infinities break a lot of
>>>> common sense).
>>>>
>>>>
>>>> A key point about your 'static' variable problem.
>>>
>>> There is only a single question here, not the myriad of questions that
>>> you refer to.
>>>
>>> Does my use of a single static variable that holds the ongoing execution
>>> trace by itself necessarily completely disqualify my system from
>>> applying to the halting problem or not?
>>>
>>> a) Yes
>>> b) No
>>
>> Error of the Complex Question, just like the question of "Have you
>> stopped lying about your Halt Decider?".
>>
>> It isn't the existence of a static variable itself that might disqualify
>> your system for applying to the halting problem,
>
> André disagrees so one of you must be wrong.

Then take his answer and go away as you admit defeat.

>
>>  but does the existence
>> of that variable, and the way that your program uses it mean that H is
>> not an actual Computation. The existence of the variable opens the door
>> to it being disqualified, but the actual disqualification needs more
>> information.
>>
>> If EVERY call to H(P,I) for a given P and I returns the exact same
>> answer every time, then H is still a computation.
>>
>> The key point here is that When H decides on the call H(P,P) and in that
>> simulation of P(P) there is a call to H(P,P) then the 'correct' answer
>> for H needs to take into account that this simulated WILL do exactly the
>> same thing as the H that is doing the simulation, so if the simulating H
>> is going to answer Non-Halting, the behavior of the simulated machine
>> will be based on that simulated H also returning that same answer. Yes,
>> H is not going to have simulated to that point of the simulated machines
>> execution, so the simulating H will not be able to see that result, but
>> that IS the behavior of the machine that it is simulating, and thus
>> affect what is the 'Right' answer for H to give.
>>
>>>
>>>> If H really WAS a real
>>>> simulator, then there is no issue with the static variable as only one
>>>> copy of H is actually execution, all the other copies are just
>>>> simulation, so the one variable holding the execution trace hold the
>>>> execution trace of the simulation that it is doing, and there is no
>>>> issue.
>>>>
>>>> The only way that the issue you describe becomes a real issue is if H
>>>> doesn't ACTUALLY simulate/debug step through copies of itself, but
>>>> applies some sort of 'transform' to the execution, and you need to have
>>>> some very good proof that this transform is actually valid, and that
>>>> the
>>>> resulting H, which passes data to embedded copies of itself, and thus
>>>> knows of stuff of its environment beyond what it is supposed to know is
>>>> actually the equivalent of the decider that doesn't do any of that
>>>> 'illegal' operations. My guess is that your H is actually NOT the
>>>> equivalent of such an actual computation and does actually behave
>>>> differently depending on execution environment, and thus fails to meet
>>>> the basic requirements.
>>>>
>>>> Remember, if the H inside H^ doesn't behave exactly identical to the H
>>>> that is deciding on that H^, then you aren't working on the right
>>>> definitions of the system.
>>>>
>>>> This seems to be one of your fundamental tripping point, and is one of
>>>> the issues with doing proofs like this in non-Turing Machine
>>>> environment
>>>> (like C/x86 or even RASP) that 'code fragments' can be non-computations
>>>> and thus not the equivalent of a Turing Machine.
>>>>
>>>
>>>
>>
>
>


Click here to read the complete article
Re: Why do theory of computation problems require pure functions?

<si50iu$960$1@dont-email.me>

 copy mid

https://www.novabbs.com/devel/article-flat.php?id=21290&group=comp.theory#21290

 copy link   Newsgroups: comp.theory
Path: i2pn2.org!i2pn.org!news.swapon.de!eternal-september.org!reader02.eternal-september.org!.POSTED!not-for-mail
From: polco...@gmail.com (olcott)
Newsgroups: comp.theory
Subject: Re: Why do theory of computation problems require pure functions?
Date: Sat, 18 Sep 2021 10:28:27 -0500
Organization: A noiseless patient Spider
Lines: 43
Message-ID: <si50iu$960$1@dont-email.me>
References: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>
<si3r5q$8ln$1@dont-email.me> <KZSdncvVqtDkctj8nZ2dnUU7-f_NnZ2d@giganews.com>
<ZVm1J.3937$7U3.2717@fx24.iad>
<j8adnV6gzfcKYdj8nZ2dnUU7-V3NnZ2d@giganews.com> <si4v1h$u4l$2@dont-email.me>
<rvn1J.130329$o45.114860@fx46.iad>
Mime-Version: 1.0
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Date: Sat, 18 Sep 2021 15:28:30 -0000 (UTC)
Injection-Info: reader02.eternal-september.org; posting-host="bc1a1bc5547333190b7888a63eca096f";
logging-data="9408"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX1+rz+PgELNTXFmWmhC4PPky"
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:78.0) Gecko/20100101
Thunderbird/78.14.0
Cancel-Lock: sha1:j1JH1Xey8o/bHhcnYZWkG4xZAJg=
In-Reply-To: <rvn1J.130329$o45.114860@fx46.iad>
Content-Language: en-US
 by: olcott - Sat, 18 Sep 2021 15:28 UTC

On 9/18/2021 10:23 AM, Richard Damon wrote:
> On 9/18/21 11:02 AM, André G. Isaak wrote:
>> On 2021-09-18 08:49, olcott wrote:
>>> On 9/18/2021 9:43 AM, Richard Damon wrote:
>>
>>> Does my use of a single static variable that holds the ongoing
>>> execution trace by itself necessarily completely disqualify my system
>>> from applying to the halting problem or not?
>>>
>>> a) Yes
>>> b) No
>>
>> (a) Yes.
>>
>> André
>>
>
> That is incorrect, as it is quite possible to have a program that IS a
> computation that still has a static variable, it a categorical No can be
> disproven.
>
> If his halt decider does ACTUALLY SIMULATE the provided program (and not
> execute it under a debugger) then in the execution context of the
> decider never actually has any recursion occurring, so only one copy of
> the decider ever sees that value of that variable at any given time.
>
> Yes, it appears that the way his current design works, the static
> variable provides an information back channel between different 'levels'
> of the decider running and that affects the behavior of the different
> 'levels' so it is not a Computation, but the mere presence of a static
> variable isn't enough.
>
> For example, the common trick of memoizing a function to save previous
> calculated results to make it run faster does not in of itself
> disqualify a function from being a true computation.
>

Only the master UTM / halt decider makes the halt status decision.
The slave UTM halt deciders merely update the execution trace data.

--
Copyright 2021 Pete Olcott "Great spirits have always encountered
violent opposition from mediocre minds." Einstein

Pages:12345678910
server_pubkey.txt

rocksolid light 0.9.7
clearnet tor