The Modified Halting Problem, Take ??? .

I. The Claim.

The claim has been made that the following, or a variant
thereof, is an ill-formed question. [*]

Given a codestring S and a parameter-array A, determine
whether the lambda-call S(A) will return a result in
a finite amount of time, or endlessly loop.

I for one dispute that claim, although one might ask what
a codestring is, as the original was done more rigorously
through a Turing-machine system, which had a state set,
a transition function, a start state, and one or more
halting-states. (I consider my way simpler, and more in
line with current coding practices; it shouldn't matter,
though.)

So first, some definitions.

II. Definitions.

1. A codestring is a series of codons each of which can do the following:

* Arithmetic operations on scratch areas.
* Fetches from the parameter area. For purposes of simplicity we'll
assume a stack-based parameter area which the codestring can push
to and pop from.
* Conditional jumps to somewhere within the codestring. If the
execution tries to go outside the codestring the machine will do
something reasonable; most likely it will simply either go to the
start of the codestring or exit as it goes off the end. The
jumps can be absolute or relative; relative is probably
preferable.
* An "EXIT" primitive which terminates execution of the codestring,
leaving the result in a known place which can be retrieved by the
executer of the codestring. (For most machines that's R0; for the
ix86 primitives that's most likely EAX. For purposes of this problem
we'll assume registers that can store indefinitely big strings or
integers, with R0 being the designated return register.)
The codestring can also exit by falling off the end.

2. A parameter-array is a series of strings, numbers, or
parameter-arrays which can be fetched
by the codons in a code-string. This
recursive definition allows constructs such as
[['Anaconda',1,['Bollixed',2.0],['Cantor'],[]],3.45].
When done in the context of a lambda-call one replaces
the outer [] with parentheses. For now we'll ignore
the question of checking for well-formedness, and issues
such as quotes-within-quotes.

3. A lambda-call is a codestring fed with a parameter array. The
lambda-call, if it exits, can be considered a function, and is here
written as S(A) for the codestring S and parameter-array A.

III. Computability of the halting-function.

So now the question forks.

A: Can one always answer the halting question?
B: Can one answer the halting question using a codestring implementation
of its own?

(A) first. A is true, for one can simply define R_i(S,A),
which is basically the machine stepped through i iterations
as it executes the codestring. Then S(A) halts if R_i(S,A)
indicates the machine stopped for some nonnegative integer
i, and S(A) does not halt if R_i(S,A) halts for no i.
One can also define this as H(S,A) = lim(i->+oo) H_i(S,A),
where H_i(S,A) is true if R_i(S,A) is a halted state,
or for some j < i, R_j(S,A) is a halted state.

Granted, H() may not be a computable function, for the heat
death of the Universe may occur first. But mathematicians
don't have a problem with that, and compute sums such as
sum(i=1,+oo) (1/2^i) all the time -- though the methods are
usually a little smarter than

GeometricSumString = 'Mov #1.0, R1;
Mov #0, R0;
L1:
Div #2.0, R1;
Add R1, R0;
Jmp L1;'

It's pretty obvious to humans that this will never halt,
though were we to have a computer that could run for
an infinite length of time R0 will have the value 2.0
(and R1 the value 0.0). Of course there might be other
questions that we'd want to put to it first, such as
"how can we get everyone to peaceably and sustainably live
together in harmony?" and "how would we cure all disease?".
But I digress. [+]

Also, we might not know the answer to H() for given
codestrings (e.g., the smallest even number > 2 that
cannot be represented as the sum of two primes -- the
Goldbach Conjecture), but that doesn't mean it's not one
or the other; we just don't know which one. Of course,
that's part of the fun...

(B) involves a codestring Sh. Sh([S,A]) will compute whether S(A) will
halt, in theory. In practice, it doesn't quite work.

Consider an arbitrary codestring S, and construct the following
codestring W<S> therefrom.

W<S> = 'Push ParameterArea; Push ParameterArea(0);' + S
+ 'Pop; Pop; Test R0; Stuck: JTrue Stuck'

(Since a ParameterArea is an array this is possible.)

Clearly, W<S> is a valid codestring if S is. This is *not* a subroutine
call, but merely a method by which, given one codestring, I construct
another -- one might call this a _meta_algorithm_.

We now try to determine the value of Sh(W<Sh>, [W<Sh>]).

If Sh(W<Sh>,[W<Sh>]) is TRUE, then this means W<Sh>(W<Sh>,[W<Sh>]) halts.
However, if W<Sh>(W<Sh>,[W<Sh>]) halts then Sh(W<Sh>,[W<Sh>]) had to
have returned FALSE. Either Sh() is malfunctioning or our assumption
was wrong.

If Sh(W<Sh>,[W<Sh>]) is FALSE, then this means W<Sh>(W<Sh>,[W<Sh>]) loops.
However, if W<Sh>(W<Sh>,[W<Sh>]) loops then Sh(W<Sh>,[W<Sh>]) had to
have returned TRUE. Either Sh() is malfunctioning or our assumption
was wrong again.

Contradiction. Hence (B) is untrue. Of course W<Sh> is
highly contrived, which is probably what led Peter Olcott
to believe there is a workaround for this problem.

IV. Modifications to salvage the implementation.

The question has now forked again.

(C) Can one answer the halting question using a codestring
implementation on some strings, but not on all strings?

Clearly, yes. We can for instance return "True", "False", or "Punt".
One valid implementation of Sh is simply

Sh = 'MOV #Punt,R0; Exit;'

which simply punts on everything. Therefore the modified halting
problem is solvable, if uselessly so.

One can of course put more code in Sh; for example, one might compare
the first parameter to a series of known algorithms that have been
previously determined by other means to always halt, always loop,
or both.

Various heuristics can also be done; for example, one can determine
whether part of a code string fits the pattern


S = '... ; Mov #n, Rv; L1: Cmp #0, Rv; JEqual LEnd; ...; Decr Rv; Jmp L1;
LEnd:...'

which is basically a FOR loop, and Rv is not stored into nor does the
routine try to jump out of the loop. While this is indeed possible
there are other forms of loops (Douglas Hofstadter refers to them as
"mu-loops"), which may or may not terminate.

V. Malignant_Self_Reference.

Peter Olcott's claim is that one can test -- somehow
-- to see if W<Sh> has a Malignant_Self_Reference.
Trouble is, W<Sh> has *no references at all*; it's merely
a codestring which just happens to be constructed from
another codestring. One might even algorithmically
implement W (the results require more primitives than
I've defined here, but it's just a string concatenation).
But how can a codestring check for a self-reference when
it can't possibly refer to itself? This was a *deliberate*
design decision, and still one can derive the contradiction
in section III.

VI. A useless Codestring modification.

Codestrings can operate on registers, which are a variant
of "scratch area" mentioned earlier. For purposes of this
discussion we'll assume an indefinite set of registers R0,
R1, R2, ... . Clearly, for a given codestring implementing
two operations

S1 = '...; Mov R1, R2; Mov R3, R4; ...'

we can generate another codestring

S2 = '...; Mov R1, R2; Mov #0, R5; Mov R3, R4; ...'

Assuming R5 is used nowhere else in S1 this is effectively a
no-operation. In fact, one can do pretty much anything that doesn't
involve registers in RegisterSetOf(S1), as long as it terminates.
So even if Malignant_Self_Reference were possible, one merely
mutates the algorithm. There are at least countably many ways
of doing so.

VII. A useless Machine extension.

One might postulate that adding the ability to read arbitrary codewords
from itself might extend the machine. As far as I can tell, it does
not. The general idea might be

S1 = '...; Mov CodeWord(Ri),Rj; ...'

It is clear that this can be replacd by:

S2 = '...; L0: CMP Ri,#0; JFalse L1; MOV #Value_0,Rj; Jmp LEnd;
L1: CMP Ri,#1; JFalse L2; MOV #Value_1,Rj; Jmp LEnd;
...
LEnd: ...'

which computes exactly the same value if there are enough CMP
statements. S2 might be far longer than S1, but it's still finite.
Therefore this extension, which might allow for the implementation of
Malignant_Self_Reference, is unnecessary for the proposed implementation
of Sh, though it might make the implementation thereof more elegant,
were it possible at all.

(Adding the ability to *write* arbitrary codewords is beyond the scope of
this exercise. Since Turing machines can't modify their state or
transition tables this is probably not all that important anyway.)

VIII.

So...anything obvious I've missed in all of the above?

[*] this is a modified variant of the original claim, which simplifies
things for me. Therefore, this is a strawman proposal. However, it
should be equivalent at some level to the original Turing machine.

[+] it is possible to modify this slightly to compute the sum to an
arbitrarily specified positive precision.

--
#191, ewill3@xxxxxxxxxxxxx
GNU and improved.

--
Posted via a free Usenet account from http://www.teranews.com

.

Loading