memoization? ergo valid computable function (Halting Problem reprise)

[Mr Flibble]

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

[Richard Damon]

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.

[Skep Dick]

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.

[Mr Flibble]

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

[Richard Damon]

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.

[Mr Flibble]

On Sun, 31 Jul 2022 20:21:08 -0400

Which is entirely proper and correct.

/Flibble

[Richard Damon]

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.