XPost: comp.theory, sci.logic, sci.math
On 5/28/22 12:31 PM, olcott wrote:
On 5/28/2022 11:25 AM, Malcolm McLean wrote:
On Saturday, 28 May 2022 at 13:18:28 UTC+1, Andy Walker wrote:
On 28/05/2022 11:46, Mikko wrote:
On 2022-05-28 08:41:42 +0000, Malcolm McLean said:
[... various restrictions ...]
Now, unless I've nodded, I ought to be able to produce a very
simple Turing
machine which solves the halting problem for this domain.
You must also exclude directly and indirectly recursive functions.
In addition, the loop variable of a for loop must not be modified
in the loop and its address must not be given to a function that
does not promise to regard it as an address to a constant.
What the pair of you are saying is, in effect, that there is a
significant subset of programs which are guaranteed to halt, and for
which the HP is therefore trivial. Such programs even include many of
practical [eg engineering] interest. This is true, and uncontroversial.
There are also significant subsets of programs which are guaranteed not
to halt [at least in normal circumstances and short of hardware failure
or intervention]. But, no matter how you slice and dice, there is also
a substantial subset of programs whose behaviour cannot be determined
by an algorithmic examination of the code [inc input]; and the attack
on the HP via emulation and Busy Beavers shows clearly that a lot of
/very/ simple programs, and indeed problems, fall into this category.
[Not least because a UTM is a very simple program, and any complexity
relates to its input, which /could/ be a representation of a UTM and
/its/ input, which could be ....]
As ever, although the HP is expressed in terms of halting, it
equally applies to problems such as "Does my program ever reach line
23?", or "Does it ever produce any output?" or "Does it produce the
same output as your program?", which may be of more practical interest.
Yes, in line with what Malcolm is proposing, it's possible to produce
analysers, perhaps even of commercial interest, which often say useful
things about some code; but there are always areas of doubt, and
every time you explore one of these another can of worms opens up.
A partial answer for practical programming lies in disciplined
code, with carefully designed pre- and post-conditions, etc., etc. But
that doesn't help with programs written without that discipline, and it
doesn't help to solve the Goldbach Conjecture.
PO seemed to be going down the route of saying that some programs
are not in the domain of his halt decider. Whilst that prompted ridicule,
it's not actually an inherently bad approach, depending what you want
to achieve.
A halt decider must only compute the mapping from its input to an accept
or reject state based on the actual behavior specified by this input.
NON-INPUTS DO NOT COUNT
NON-INPUTS DO NOT COUNT
NON-INPUTS DO NOT COUNT
It is the case that the correct x86 emulation of the input to H(P,P) by
H would NEVER reach the "ret" instruction of P therefore H(P,P)==0 is
proved to be correct.
And in what way is the "representation" or P/H^ not an input?
The problem is Given a representation, determine the halitng behavior.
Thus the behavior of the machine represented by the input not a
"non-input" but the goal of the decider itself. If it isn't, then it
isn't a Halt Decider.
"The Actual Behavior specified by this input" for H(M,w) is the behavior
of M(w) BY DEFINITION, so this CAN'T be just defined as a "NON-INPUT",
unless you want to just define that Halt Decider just can't exist.
FAIL.
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)