If memoization is a valid technique in the realm of "computable
functions" then it is entirely valid for my halting function to return
both true and false without actually deciding its input ergo allowing a
simulating halt decider to be implemented without the use of recursion.

/Flibble

On 7/31/22 6:54 PM, Mr Flibble wrote:
> If memoization is a valid technique in the realm of "computable
> functions" then it is entirely valid for my halting function to return
> both true and false without actually deciding its input ergo allowing a
> simulating halt decider to be implemented without the use of recursion.
>
> /Flibble
>

Memoization does NOT allow a function to return different values for the
same input.

Memoization just means that the function caches input-output pairs and
doesn't compute the value if it has saved the value it would return.

On Monday, 1 August 2022 at 00:54:12 UTC+2, Mr Flibble wrote:
> If memoization is a valid technique in the realm of "computable
> functions" then it is entirely valid for my halting function to return
> both true and false without actually deciding its input ergo allowing a
> simulating halt decider to be implemented without the use of recursion.
>
> /Flibble

What does memoization have to do with the other thing?

A function which returns different results for the same input (a non-deterministic function) is not memoizable.

If you memorize (cache) the result of a non-memoizable function you will soon discover the hellhole called cache invalidation.

On Sun, 31 Jul 2022 19:05:35 -0400
Richard Damon <Richard@Damon-Family.org> wrote:

> On 7/31/22 6:54 PM, Mr Flibble wrote:
> > If memoization is a valid technique in the realm of "computable
> > functions" then it is entirely valid for my halting function to
> > return both true and false without actually deciding its input ergo
> > allowing a simulating halt decider to be implemented without the
> > use of recursion.
> >
> > /Flibble
> >
>
> Memoization does NOT allow a function to return different values for
> the same input.
>
> Memoization just means that the function caches input-output pairs
> and doesn't compute the value if it has saved the value it would
> return.

I know what memoization means and you are missing the point: if a
memoized function *invocation* is allowed to return a result without
evaluating its parameters then I can do a similar thing with my
halting function. Also my halting function *is* returning the same
thing for the same inputs: it is return true *and* false.

/Flibble

On 7/31/22 7:57 PM, Mr Flibble wrote:
> On Sun, 31 Jul 2022 19:05:35 -0400
> Richard Damon <Richard@Damon-Family.org> wrote:
>
>> On 7/31/22 6:54 PM, Mr Flibble wrote:
>>> If memoization is a valid technique in the realm of "computable
>>> functions" then it is entirely valid for my halting function to
>>> return both true and false without actually deciding its input ergo
>>> allowing a simulating halt decider to be implemented without the
>>> use of recursion.
>>>
>>> /Flibble
>>>
>>
>> Memoization does NOT allow a function to return different values for
>> the same input.
>>
>> Memoization just means that the function caches input-output pairs
>> and doesn't compute the value if it has saved the value it would
>> return.
>
> I know what memoization means and you are missing the point: if a
> memoized function *invocation* is allowed to return a result without
> evaluating its parameters then I can do a similar thing with my
> halting function. Also my halting function *is* returning the same
> thing for the same inputs: it is return true *and* false.
>
> /Flibble
>

Memoization requires that the cache value be the correct answer for that
input. The parameters to the function are still "evaluated" in the sense
that we know that actual value being passed.

Note, your function isn't ACTUALLY returning True and False, it is doing
test executions in its simulation to see if either answer could be
correct. It has sort of gotten around the requirement of a pure function
to always return a single value for a given set of parameter by doing so
ONLY in its INTERNAL simulation of the input.

The key is no actual routine outside of H ever sees that value, at least
until H decides which answer it is going to give and return it.

The "returning" is only an aspect of the simulation that it is
performing, and not observable by the outside world.

On Sun, 31 Jul 2022 20:21:08 -0400
Richard Damon <Richard@Damon-Family.org> wrote:

> On 7/31/22 7:57 PM, Mr Flibble wrote:
> > On Sun, 31 Jul 2022 19:05:35 -0400
> > Richard Damon <Richard@Damon-Family.org> wrote:
> >
> >> On 7/31/22 6:54 PM, Mr Flibble wrote:
> >>> If memoization is a valid technique in the realm of "computable
> >>> functions" then it is entirely valid for my halting function to
> >>> return both true and false without actually deciding its input
> >>> ergo allowing a simulating halt decider to be implemented without
> >>> the use of recursion.
> >>>
> >>> /Flibble
> >>>
> >>
> >> Memoization does NOT allow a function to return different values
> >> for the same input.
> >>
> >> Memoization just means that the function caches input-output pairs
> >> and doesn't compute the value if it has saved the value it would
> >> return.
> >
> > I know what memoization means and you are missing the point: if a
> > memoized function *invocation* is allowed to return a result without
> > evaluating its parameters then I can do a similar thing with my
> > halting function. Also my halting function *is* returning the same
> > thing for the same inputs: it is return true *and* false.
> >
> > /Flibble
> >
>
> Memoization requires that the cache value be the correct answer for
> that input. The parameters to the function are still "evaluated" in
> the sense that we know that actual value being passed.
>
> Note, your function isn't ACTUALLY returning True and False, it is
> doing test executions in its simulation to see if either answer could
> be correct. It has sort of gotten around the requirement of a pure
> function to always return a single value for a given set of parameter
> by doing so ONLY in its INTERNAL simulation of the input.
>
> The key is no actual routine outside of H ever sees that value, at
> least until H decides which answer it is going to give and return it.
>
> The "returning" is only an aspect of the simulation that it is
> performing, and not observable by the outside world.

Which is entirely proper and correct.

/Flibble

On 7/31/22 8:23 PM, Mr Flibble wrote:
> On Sun, 31 Jul 2022 20:21:08 -0400
> Richard Damon <Richard@Damon-Family.org> wrote:
>
>> On 7/31/22 7:57 PM, Mr Flibble wrote:
>>> On Sun, 31 Jul 2022 19:05:35 -0400
>>> Richard Damon <Richard@Damon-Family.org> wrote:
>>>
>>>> On 7/31/22 6:54 PM, Mr Flibble wrote:
>>>>> If memoization is a valid technique in the realm of "computable
>>>>> functions" then it is entirely valid for my halting function to
>>>>> return both true and false without actually deciding its input
>>>>> ergo allowing a simulating halt decider to be implemented without
>>>>> the use of recursion.
>>>>>
>>>>> /Flibble
>>>>>
>>>>
>>>> Memoization does NOT allow a function to return different values
>>>> for the same input.
>>>>
>>>> Memoization just means that the function caches input-output pairs
>>>> and doesn't compute the value if it has saved the value it would
>>>> return.
>>>
>>> I know what memoization means and you are missing the point: if a
>>> memoized function *invocation* is allowed to return a result without
>>> evaluating its parameters then I can do a similar thing with my
>>> halting function. Also my halting function *is* returning the same
>>> thing for the same inputs: it is return true *and* false.
>>>
>>> /Flibble
>>>
>>
>> Memoization requires that the cache value be the correct answer for
>> that input. The parameters to the function are still "evaluated" in
>> the sense that we know that actual value being passed.
>>
>> Note, your function isn't ACTUALLY returning True and False, it is
>> doing test executions in its simulation to see if either answer could
>> be correct. It has sort of gotten around the requirement of a pure
>> function to always return a single value for a given set of parameter
>> by doing so ONLY in its INTERNAL simulation of the input.
>>
>> The key is no actual routine outside of H ever sees that value, at
>> least until H decides which answer it is going to give and return it.
>>
>> The "returning" is only an aspect of the simulation that it is
>> performing, and not observable by the outside world.
>
> Which is entirely proper and correct.
>
> /Flibble
>

Which says your memoized decider hasn't actually returned True AND False.

It only simulated returning True and simulated returning False, and did
these before it actually knows what value it is going to actually return
to memoize.

The act of memoizing hasn't changed what the decider has done, or needs
to do. Just means that if the program asks the SAME halting decision,
you have saved what you are going to return.