Rocksolid Light

Welcome to novaBBS (click a section below)

mail  files  register  nodelist  faq  login

I wish you humans would leave me alone.


computers / comp.ai.philosophy / Re: Why do theory of computation problems require pure functions? [ computation ? ]

Subject: Re: Why do theory of computation problems require pure functions? [ computation ? ]
From: olcott
Newsgroups: comp.theory, comp.ai.philosophy, sci.logic, sci.math
Date: Tue, 21 Sep 2021 15:16 UTC
References: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
X-Received: by 2002:a37:a13:: with SMTP id 19mr1733218qkk.497.1632237378541;
Tue, 21 Sep 2021 08:16:18 -0700 (PDT)
Path: i2pn2.org!i2pn.org!weretis.net!feeder6.news.weretis.net!news.misty.com!border2.nntp.dca1.giganews.com!news-out.google.com!nntp.google.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!buffer1.nntp.dca1.giganews.com!news.giganews.com.POSTED!not-for-mail
NNTP-Posting-Date: Tue, 21 Sep 2021 10:16:13 -0500
Subject: Re: Why do theory of computation problems require pure functions? [
computation ? ]
Newsgroups: comp.theory,comp.ai.philosophy,sci.logic,sci.math
References: <a7WdnftR4JAUzNj8nZ2dnUU7-d_NnZ2d@giganews.com>
<0LKdnQW0_vXAz9v8nZ2dnUU7-RHNnZ2d@giganews.com> <si5o18$ca0$1@dont-email.me>
<b8qdnUQWUNeC-Nv8nZ2dnUU7-cvNnZ2d@giganews.com> <si5p69$qpa$1@dont-email.me>
<i6WdnR3uOcyR9Nv8nZ2dnUU7-TGdnZ2d@giganews.com> <si5qpm$srv$1@dont-email.me>
<b885b582-6153-4184-8dad-aed5dfc83cecn@googlegroups.com>
<87bl4o9rfk.fsf@bsb.me.uk>
<9f3d89f7-6040-4d9f-96e8-4fb18bf6985fn@googlegroups.com>
<877dfc891e.fsf@bsb.me.uk>
<95d4a88f-8fbe-4151-a6bf-c83103d77f1bn@googlegroups.com>
<GdSdnbDQ5umIf9r8nZ2dnUU7-UednZ2d@giganews.com> <875yuv7ei8.fsf@bsb.me.uk>
<i96dnQP238RsBdX8nZ2dnUU7-XPNnZ2d@giganews.com> <87fsty6gxi.fsf@bsb.me.uk>
<VtmdnSy6oZ3Jh9T8nZ2dnUU7-XvNnZ2d@giganews.com> <877dfa6bm8.fsf@bsb.me.uk>
<me2dnZOPq6pzvtT8nZ2dnUU7-Q3NnZ2d@giganews.com>
<Acb2J.135913$o45.5370@fx46.iad>
<mOidnQHsVe4z39T8nZ2dnUU7-VfNnZ2d@giganews.com>
<Lcc2J.32916$GD7.26784@fx23.iad>
<xsednYAjH-48xNT8nZ2dnUU7-U3NnZ2d@giganews.com>
<Bod2J.35998$nR3.3757@fx38.iad>
From: NoO...@NoWhere.com (olcott)
Date: Tue, 21 Sep 2021 10:16:12 -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: <Bod2J.35998$nR3.3757@fx38.iad>
Message-ID: <-YmdnTDXGqGgatT8nZ2dnUU7-U_NnZ2d@giganews.com>
Lines: 253
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-SWeYC3TsFYCaYPBk2Dg3pNYTMtYsDjPqGvHJFxDRvo4cMH352fPyHGDcURWnJalG1IoCp1c0aWp+dMa!HwUI/DN78kPG5rC7WKEXdqDl/3/9eDD+QnyUIoaNxI0WDD/0Lt+UuTFLOlJtnm86oYoolHIZlN8=
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: 12723
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 8bit
View all headers
On 9/20/2021 11:42 PM, Richard Damon wrote:
On 9/21/21 12:03 AM, olcott wrote:
On 9/20/2021 10:21 PM, Richard Damon wrote:
On 9/20/21 10:25 PM, olcott wrote:
On 9/20/2021 9:12 PM, Richard Damon wrote:
On 9/20/21 8:14 PM, olcott wrote:
On 9/20/2021 7:00 PM, Ben Bacarisse wrote:
olcott <NoOne@NoWhere.com> writes:

On 9/20/2021 5:06 PM, Ben Bacarisse wrote:
olcott <NoOne@NoWhere.com> writes:

On 9/20/2021 5:00 AM, Ben Bacarisse wrote:
olcott <NoOne@NoWhere.com> writes:

The two machines are already fully operational.
H1 is merely a copy of H.
It's deceptive to call your secret C functions "machines".  It
hints at
the formality a clarity of Turing machines, but a TM that is a
copy of
another will have exactly the same transfer function (i.e. it
will
never
compute a different result).

Unless one of them has a pathological self-reference relationship
with
its input and the other one does not.
No.  I stated a fact (about TMs) that has no exceptions.  Your
secret C
code is another matter, of course.  It's just the deception of
calling
your code a "machine" that I was objecting to.  It gives your
hidden
code an air of formality that it lacks.

This is easily proven in a way that you are incapable of
understanding.

You can't even write English.  Saying "This is easily proven"
following
a quote from me that you are wrong, means you can easily prove what I
said in the quote -- that you are wrong.  That is indeed the case,
but
it is unlikely to be what you meant to say.

Your junk functions are not "machines".  The terms suggests an
undeserved formality.


void P(u32 x)
{
     if (H(x, x))
       HERE: goto HERE;
}

The actual correct x86 emulation of the input to H1(P,P) is different
than the actual correct x86 emulation of the input to H(P,P).

Which means that your emulator is broken, or H isn't a Computation.

PERIOD.


That would mean that "a computation" cannot possibly determine that it
has been invoked in infinitely recursive simulation, whereas a C
function with a a pair of static local variables can.


Right, it can't

Yep, a C code fragment can easily be a non-computation.

This means that a C function can do something that a TM cannot do thus
making it strictly more powerful than a TM. Since this seems implausible
I estimate that you are simply wrong.

Nope.

The Rule is that there is no COMPUTATION that the C function can do that
a Turing Machine can not do. This is the definition of Turing
Competeness and the Turing Equivalence rule.


Yes a C function can determine that it has been called in infinitely
nested simulation only because it is able to maintain static local data
that is not erased between nested simulations.

If a TM cannot maintain static data between nested simulations then a TM
cannot detect when it is within infinitely nested simulations. This
makes the C function strictly more powerful than the TM.

Maybe, but it doesn't mean it can COMPUTE something that a Turing
Machine can, which is the only thing that Computation Theory is
concerned with.

If it isn't a pure mapping of an input to an output, Computation Theory
doesn't care about it.


Also, any 'complete' program (or complete fragment) that has a well
defined input, can be expressed as a Computation, and thus a Turing
Machine could do the equivalent of it. The key here is COMPLETE. You
function isn't 'Complete' as exection goes outside of it and then comes
back in.

Exactly the same way that the simulation of the

machine description of a UTM H that simulates
the machine description P the simulates

machine description of a UTM H that simulates
the machine description P the simulates

machine description of a UTM H that simulates
the machine description P the simulates ...

Olcott H can detect when Olcott P is doing this only because Olcott H
has static local data the survives nested simulations.

If a TM cannot have such static local data then Olcott H is strictly
more powerful than Linz H.



Right, if H IS just a UTM, then H^ is non-halting, but then H doesn't
give an answer to the question H(H^,H^), so it can't answer the question.


Although Olcott H can watch the nested simulation of itself because it has static local data Linz Ĥ could not do this if it is not allowed to have the equivalent of static local data. This would make Olcott H strictly more powerful that Linz Ĥ, when Linz Ĥ is arbitrarily forbidden from having its own static local data.

Once H has the code to abort the simulation loop, and is also still a

We can get here because the Linz Ĥ cannot even get to the point where the abort criteria is matched because it is forced to erase the execution data that would show this.

Computation, then H^ will no longer be stuck in an infinite recursion as
the H inside it will ALSO do that same abort to keep it out of the loop,
and H when coming up with its answer needs to take that into account to
give the right answer.


This never happens. Ĥ must see at least two iterations and without static local data it can at most only see one.

The fact that you can write a program that can detect this sort of
recusion doesn't matter to Computation Theory, it is only concerned
about actual Computations,

It does not make sense that arbitrary rules would allow a C function to be strictly more powerful than a TM so you must be wrong.

and a proper Halt Decider on Computation MUST
be a Computation, as the behavior of a Computaton only depends on the
Machine/ALgorithm and the Input Data, so ANY decider that changes its
answer based on something outside that CAN'T be right, by definition, it
give two different answers for a question that always has the same
answer, so it MUST be wrong at time.


In the case of Olcott H, H merely provides no answer at all until (1) It has seen a behavior pattern that proves that its input matches a never halting behavior pattern (2) Its input halts on its own.

The key here is that if H isn't a Computation, then the 'machine' H^
isn't either, so Computation Theory doesn't care about what it does.


So a halt decider can be made yet it breaks arbitrary rules so no one cares that a halt decider can be made.

The Halting Problem of Computation Theory is STRICTLY about actual
Computations.

If your H ACTUALLY is a correct decider for ALL Turing Machines, then by
definition it needs to be actually a Computation for ANY Turing Machine
given to it, and thus, it can be shown that there does actually exist a
Turing Machine version of it that can take any Turing Machine as an
input. Since this Turing Machine version IS actually a Computation, we
can use the Linz ^ trick on it showing that it gets this case wrong.

It doesn't make sense that a C function can be strictly more powerful that a TM in that it can detect when itself is stuck in finitely nested simulation and a TM cannot do this because it is not allowed to use static local memory therefore you are probable wrong.

The function return values are identical for identical arguments (no variation with local static variables, non-local variables, mutable reference arguments or input streams). https://en.wikipedia.org/wiki/Pure_function

The return values are identical for identical arguments, without static data there is no return value at all.


The only way we can't do this is if your H isn't a computation for some
P(I) so that there isn't a Turing Machine equivalent for it, but then
there are some conditions under which H calls P(I) both Halting and
Non-Halting, so there are some conditions where it gives the wrong
answer, so it isn't the Universal Halt Decider that COmputation Theory
is Looking for.


In those cases where H(P,P) gives and answer that is inconsistent with the behavior of P(P) H1(P,P) gives an answer that is consistent with the behavior of P(P).

We cannot correctly call this a wrong answer because it is a verifiable fact that the input to H(P,P) never halts and H correctly reports this.

The inconsistency is not because H(P,P) is wrong, it is because when H(P,P) aborts the infinitely recursive simulation at any point besides the first infinitely recursive invocation the sequence ceases to be infinitely recursive and then the earlier parts of this infinitely recursive simulation chain come to a halt.

We can know for sure that the whole chain is infinitely recursive when none of the invocations is ever terminated then the chain never halts.

Again, note that if Olcott-H is NOT a strict computation when given an
actual Turing Machine/Input (or equivalent), then BY DEFINTION it must
be wrong some of the time, as to be a non-computation says that there IS
some condition where for an actual computation is predicts both Halting
and Non-Halting for the exact same computation, and thus one of the
answers MUST be wrong.


Self-contradictory inputs derive inconsistent results. The simplest thing to do is simply detect and reject such inputs.

u32 PSR_Olcott_2004(u32 P)
{
   return H1(P,P) != H(P,P);
}

"This sentence is not true" is rejected as a semantically ill-formed truth bearer on the basis that it is self-contradictory.

"This sentence cannot be proven." is rejected as a semantically ill-formed truth bearer on the basis that it is self-contradictory.


--
Copyright 2021 Pete Olcott

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


SubjectRepliesAuthor
o Why do theory of computation problems require pure functions?

By: olcott on Sat, 18 Sep 2021

13olcott
rocksolid light 0.7.2
clearneti2ptor