Do all TM running an decision algorithm give the same answer?
For example, translation of algorithm could behave differently by the program's size?
If so, this may be a way to make the HP proof invalid.

wij <wyniijj2@gmail.com> writes:

> Do all TM running an decision algorithm give the same answer?

If you are talking about halt decision algorithms, then there are none
so it's an odd question.

> For example, translation of algorithm could behave differently by the
> program's size? If so, this may be a way to make the HP proof
> invalid.

A proof is not "made" invalid. It's invalid if (and only if) it is not
a correct chain of reasoning. If such a simple proof is invalid, you
should be able to point out the step that does not follow.

--
Ben.

On Thursday, 7 July 2022 at 23:59:41 UTC+1, wyni...@gmail.com wrote:
> Do all TM running an decision algorithm give the same answer?
> For example, translation of algorithm could behave differently by the program's size?
> If so, this may be a way to make the HP proof invalid.
>
TMs calculate a function. There is one set of symbols on the tape when the TM is
run, and another set when it halts. And it's deterministic, so for each possible
input there is only one possible output. Sometimes people say that the halt state
can be "accept" or "reject" and this is part of the function, but that's just a detail.

However you can have more than one TM that calculates the same function. For instance
there are several ways you could add two binary numbers. You could do it using a high school
math type algorithm with "carry" states. Or you could convert both to unary, add trivially,
then convert back to binary. Or you could decrement one number until it went to zero whilst
incrementing the other. All correct TMs that calculate the "sum" function must give the
same answer, because of the way we define "function", which is a mapping of input to
output. But they needn't use the same algorithm.

On 7/7/2022 6:41 PM, Malcolm McLean wrote:
> On Thursday, 7 July 2022 at 23:59:41 UTC+1, wyni...@gmail.com wrote:
>> Do all TM running an decision algorithm give the same answer?
>> For example, translation of algorithm could behave differently by the program's size?
>> If so, this may be a way to make the HP proof invalid.
>>
> TMs calculate a function. There is one set of symbols on the tape when the TM is
> run, and another set when it halts. And it's deterministic, so for each possible
> input there is only one possible output. Sometimes people say that the halt state
> can be "accept" or "reject" and this is part of the function, but that's just a detail.
>
> However you can have more than one TM that calculates the same function. For instance
> there are several ways you could add two binary numbers. You could do it using a high school
> math type algorithm with "carry" states. Or you could convert both to unary, add trivially,
> then convert back to binary. Or you could decrement one number until it went to zero whilst
> incrementing the other. All correct TMs that calculate the "sum" function must give the
> same answer, because of the way we define "function", which is a mapping of input to
> output. But they needn't use the same algorithm.

I just want to point out that if T is a Turing machine that halts for
any input, then there is a countably infinite set of Turing machines
that produce the same output for each possible input. [If a machine does
not halt for same states, we can make almost clones that also don't halt
for those states.] Given that fact, I think the original poster should
clarify what he has in mind.
--
Jeff Barnett

On Friday, 8 July 2022 at 10:21:05 UTC+8, Jeff Barnett wrote:
> On 7/7/2022 6:41 PM, Malcolm McLean wrote:
> > On Thursday, 7 July 2022 at 23:59:41 UTC+1, wyni...@gmail.com wrote:
> >> Do all TM running an decision algorithm give the same answer?
> >> For example, translation of algorithm could behave differently by the program's size?
> >> If so, this may be a way to make the HP proof invalid.
> >>
> > TMs calculate a function. There is one set of symbols on the tape when the TM is
> > run, and another set when it halts. And it's deterministic, so for each possible
> > input there is only one possible output. Sometimes people say that the halt state
> > can be "accept" or "reject" and this is part of the function, but that's just a detail.
> >
> > However you can have more than one TM that calculates the same function. For instance
> > there are several ways you could add two binary numbers. You could do it using a high school
> > math type algorithm with "carry" states. Or you could convert both to unary, add trivially,
> > then convert back to binary. Or you could decrement one number until it went to zero whilst
> > incrementing the other. All correct TMs that calculate the "sum" function must give the
> > same answer, because of the way we define "function", which is a mapping of input to
> > output. But they needn't use the same algorithm.
> I just want to point out that if T is a Turing machine that halts for
> any input, then there is a countably infinite set of Turing machines
> that produce the same output for each possible input. [If a machine does
> not halt for same states, we can make almost clones that also don't halt
> for those states.] Given that fact, I think the original poster should
> clarify what he has in mind.
> --
> Jeff Barnett

I thought if the story of halting decider ends because it is proven impossible would be rash:
1. The HP proof demand the H a pure function. But this is not a must of a
'halting decider', esp. for real programs. In practice, a slightly 'impure'
halting decider may be possible.
2. The counterexample P contains a function performing equivalent function of H.
I was thinking that if H could perform differently in different implements,
the HP proof won't hold (not sure of this whim). However, in real situation,
the 'bad instance P' should be rare (partly because it should be bigger and
and slower than H), real program could probably tolerate this case.

I have not used TM since learned it. My idea of TM may have several tapes or
2D tapes, basicly based on my understanding of 'hard-ware', not necessarily the one
in Linz's book. Just feel boring and thinking the opposite of the HP proof.

On 7/8/22 7:55 AM, wij wrote:
> On Friday, 8 July 2022 at 10:21:05 UTC+8, Jeff Barnett wrote:
>> On 7/7/2022 6:41 PM, Malcolm McLean wrote:
>>> On Thursday, 7 July 2022 at 23:59:41 UTC+1, wyni...@gmail.com wrote:
>>>> Do all TM running an decision algorithm give the same answer?
>>>> For example, translation of algorithm could behave differently by the program's size?
>>>> If so, this may be a way to make the HP proof invalid.
>>>>
>>> TMs calculate a function. There is one set of symbols on the tape when the TM is
>>> run, and another set when it halts. And it's deterministic, so for each possible
>>> input there is only one possible output. Sometimes people say that the halt state
>>> can be "accept" or "reject" and this is part of the function, but that's just a detail.
>>>
>>> However you can have more than one TM that calculates the same function. For instance
>>> there are several ways you could add two binary numbers. You could do it using a high school
>>> math type algorithm with "carry" states. Or you could convert both to unary, add trivially,
>>> then convert back to binary. Or you could decrement one number until it went to zero whilst
>>> incrementing the other. All correct TMs that calculate the "sum" function must give the
>>> same answer, because of the way we define "function", which is a mapping of input to
>>> output. But they needn't use the same algorithm.
>> I just want to point out that if T is a Turing machine that halts for
>> any input, then there is a countably infinite set of Turing machines
>> that produce the same output for each possible input. [If a machine does
>> not halt for same states, we can make almost clones that also don't halt
>> for those states.] Given that fact, I think the original poster should
>> clarify what he has in mind.
>> --
>> Jeff Barnett
>
> I thought if the story of halting decider ends because it is proven impossible would be rash:
> 1. The HP proof demand the H a pure function. But this is not a must of a
> 'halting decider', esp. for real programs. In practice, a slightly 'impure'
> halting decider may be possible.
> 2. The counterexample P contains a function performing equivalent function of H.
> I was thinking that if H could perform differently in different implements,
> the HP proof won't hold (not sure of this whim). However, in real situation,
> the 'bad instance P' should be rare (partly because it should be bigger and
> and slower than H), real program could probably tolerate this case.
>
> I have not used TM since learned it. My idea of TM may have several tapes or
> 2D tapes, basicly based on my understanding of 'hard-ware', not necessarily the one
> in Linz's book. Just feel boring and thinking the opposite of the HP proof.

The problem with trying to define a "Halting Decider" on a system that
allows a given program to vary its behavior based on other than its
defined input is that then Halting isn't define based on the program and
its defined input because some program might halt or not based on the
"other inputs" that aren't part of its defined input.

Also, for any program based on a finite set of definite deterministic
instructions IS a pure function when you include as its inputs
EVERYTHING that it depends on (not just its "formal" parameters), so by
locating those and defining them, you can handle any actual program.

This is one of the ways that you could try to do what Peter is doing,
give H an input that P can't control, that we set one way when WE ask
about H(P,P), and another way when we run P(P), so it gets a different H
and thus breaks the "pathological" loop by just not actually meeting the
requrements.

On 2022-07-08 11:55:58 +0000, wij said:

> On Friday, 8 July 2022 at 10:21:05 UTC+8, Jeff Barnett wrote:
>> On 7/7/2022 6:41 PM, Malcolm McLean wrote:
>>> On Thursday, 7 July 2022 at 23:59:41 UTC+1, wyni...@gmail.com wrote:
>>>> Do all TM running an decision algorithm give the same answer?

Yes, all Turing machines that implement the same decision algorithm do
give the same answer for the same parameters. However, they may differ
in the required encoding of the parameters and in the presentation of
the result. For example, one TM may require that numbers are presented
as a sequence of that many *'s and another one that they are presented
in the usual way as a sequence of digits. And one may present the result
by halting in one or another of its end states whereas another one by
writing an Y or N to the tape.

> 1. The HP proof demand the H a pure function.

No. The proof only requires what the problem requires. Otherwise it
would not be a proof.

The problem, as usually presented, requires that the solution is a
Turing machine.

It is well known that the halting problem can be solved if the requirement
that the soultion be a Turing machine is sufficiently relaxed while
keeping the restriction that the question shall be about a Turing machine.
For an oracle machine with an Turing machine halting oracle can solve it.
However, no oracle machine can solve the halting problem of an arbitrary
oracle machine.

Mikko

On 08/07/2022 12:55, wij wrote:
> I thought if the story of halting decider ends because it is proven
> impossible would be rash:> 1. The HP proof demand the H a pure function. But this is not a must of a
> 'halting decider', esp. for real programs. In practice, a slightly 'impure'
> halting decider may be possible.
> 2. The counterexample P contains a function performing equivalent function of H.
> I was thinking that if H could perform differently in different implements,
> the HP proof won't hold (not sure of this whim). [...]

None of this helps, either in theoretical terms [short of an "oracle"]
or in practical terms. You might perhaps find it more helpful to think rather
in terms of Busy Beavers [qv]. BBs and the HP stand or fall together:

-- If you have a working halt decider, then there is an algorithm to find BBs.
-- If you have an algorithm to find BBs, you can use this to construct a HD.

[Proofs very easy either way.] This is true for TMs and for any reasonable
version of either problem in C, an extended C, x86 machine code, or any other
plausible language. But the BB problem is much easier to explain, much easier
to prove insoluble, and a much more convincing result.

--
Andy Walker, Nottingham.
Andy's music pages: www.cuboid.me.uk/andy/Music
Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Mayer

On 7/8/22 8:38 AM, Mikko wrote:
> On 2022-07-08 11:55:58 +0000, wij said:
>
>> On Friday, 8 July 2022 at 10:21:05 UTC+8, Jeff Barnett wrote:
>>> On 7/7/2022 6:41 PM, Malcolm McLean wrote:
>>>> On Thursday, 7 July 2022 at 23:59:41 UTC+1, wyni...@gmail.com wrote:
>>>>> Do all TM running an decision algorithm give the same answer?
>
> Yes, all Turing machines that implement the same decision algorithm do
> give the same answer for the same parameters. However, they may differ
> in the required encoding of the parameters and in the presentation of
> the result. For example, one TM may require that numbers are presented
> as a sequence of that many *'s and another one that they are presented
> in the usual way as a sequence of digits. And one may present the result
> by halting in one or another of its end states whereas another one by
> writing an Y or N to the tape.
>
>> 1. The HP proof demand the H a pure function.
>
> No. The proof only requires what the problem requires. Otherwise it
> would not be a proof.
>
> The problem, as usually presented, requires that the solution is a
> Turing machine.
>
> It is well known that the halting problem can be solved if the requirement
> that the soultion be a Turing machine is sufficiently relaxed while
> keeping the restriction that the question shall be about a Turing machine.
> For an oracle machine with an Turing machine halting oracle can solve it.
> However, no oracle machine can solve the halting problem of an arbitrary
> oracle machine.
>
> Mikko
>

One key fact is that the Halt Decider MIGHT be possible if the decider
is a more "powerful" computation structure than the things it decides,
which means the pathological program can't be written, since it uses the
decider, so if it can't that proof breaks.

This is one of Peter's tactic, trying to define, without admitting it,
that P can't actually use a copy of H that can be asked about P,
sometimes because asking about P actually somehow becomes asking about
something else.

The problem thus is trying to find something more powerful than a Turing
Machine, able to do something that a Turing Machine can't do, the
problem being we haven't found a computation system that can do
something that beyond what a Turing Machine can do (just do it 'faster').

On 7/8/22 04:55, wij wrote:
> On Friday, 8 July 2022 at 10:21:05 UTC+8, Jeff Barnett wrote:
>> On 7/7/2022 6:41 PM, Malcolm McLean wrote:
>>> On Thursday, 7 July 2022 at 23:59:41 UTC+1, wyni...@gmail.com wrote:
>>>> Do all TM running an decision algorithm give the same answer?
>>>> For example, translation of algorithm could behave differently by the program's size?
>>>> If so, this may be a way to make the HP proof invalid.
>>>>
>>> TMs calculate a function. There is one set of symbols on the tape when the TM is
>>> run, and another set when it halts. And it's deterministic, so for each possible
>>> input there is only one possible output. Sometimes people say that the halt state
>>> can be "accept" or "reject" and this is part of the function, but that's just a detail.
>>>
>>> However you can have more than one TM that calculates the same function. For instance
>>> there are several ways you could add two binary numbers. You could do it using a high school
>>> math type algorithm with "carry" states. Or you could convert both to unary, add trivially,
>>> then convert back to binary. Or you could decrement one number until it went to zero whilst
>>> incrementing the other. All correct TMs that calculate the "sum" function must give the
>>> same answer, because of the way we define "function", which is a mapping of input to
>>> output. But they needn't use the same algorithm.
>> I just want to point out that if T is a Turing machine that halts for
>> any input, then there is a countably infinite set of Turing machines
>> that produce the same output for each possible input. [If a machine does
>> not halt for same states, we can make almost clones that also don't halt
>> for those states.] Given that fact, I think the original poster should
>> clarify what he has in mind.
>> --
>> Jeff Barnett
>
> I thought if the story of halting decider ends because it is proven impossible would be rash:
> 1. The HP proof demand the H a pure function. But this is not a must of a
> 'halting decider', esp. for real programs. In practice, a slightly 'impure'
> halting decider may be possible.
> 2. The counterexample P contains a function performing equivalent function of H.
> I was thinking that if H could perform differently in different implements,
> the HP proof won't hold (not sure of this whim). However, in real situation,
> the 'bad instance P' should be rare (partly because it should be bigger and
> and slower than H), real program could probably tolerate this case.
>
> I have not used TM since learned it. My idea of TM may have several tapes or
> 2D tapes, basicly based on my understanding of 'hard-ware', not necessarily the one
> in Linz's book. Just feel boring and thinking the opposite of the HP proof.

I haven't seen it mentioned (although I also can't be bothered to follow
all of the rambling about halting in this newsgroup) but it's perfectly
possible to prove halting for all programs in some real practical computer.

Here's someone who has discovered which programs halt on a very limited
(4-byte) computer:

https://youtu.be/ym8x8B930tM

You should try this method on the machine you're posting from and report
back the results when you've finished.

On 7/8/22 12:05 PM, Steven Paul Jobs wrote:
> On 7/8/22 04:55, wij wrote:
>> On Friday, 8 July 2022 at 10:21:05 UTC+8, Jeff Barnett wrote:
>>> On 7/7/2022 6:41 PM, Malcolm McLean wrote:
>>>> On Thursday, 7 July 2022 at 23:59:41 UTC+1, wyni...@gmail.com wrote:
>>>>> Do all TM running an decision algorithm give the same answer?
>>>>> For example, translation of algorithm could behave differently by
>>>>> the program's size?
>>>>> If so, this may be a way to make the HP proof invalid.
>>>>>
>>>> TMs calculate a function. There is one set of symbols on the tape
>>>> when the TM is
>>>> run, and another set when it halts. And it's deterministic, so for
>>>> each possible
>>>> input there is only one possible output. Sometimes people say that
>>>> the halt state
>>>> can be "accept" or "reject" and this is part of the function, but
>>>> that's just a detail.
>>>>
>>>> However you can have more than one TM that calculates the same
>>>> function. For instance
>>>> there are several ways you could add two binary numbers. You could
>>>> do it using a high school
>>>> math type algorithm with "carry" states. Or you could convert both
>>>> to unary, add trivially,
>>>> then convert back to binary. Or you could decrement one number until
>>>> it went to zero whilst
>>>> incrementing the other. All correct TMs that calculate the "sum"
>>>> function must give the
>>>> same answer, because of the way we define "function", which is a
>>>> mapping of input to
>>>> output. But they needn't use the same algorithm.
>>> I just want to point out that if T is a Turing machine that halts for
>>> any input, then there is a countably infinite set of Turing machines
>>> that produce the same output for each possible input. [If a machine does
>>> not halt for same states, we can make almost clones that also don't halt
>>> for those states.] Given that fact, I think the original poster should
>>> clarify what he has in mind.
>>> --
>>> Jeff Barnett
>>
>> I thought if the story of halting decider ends because it is proven
>> impossible would be rash:
>> 1. The HP proof demand the H a pure function. But this is not a must of a
>>    'halting decider', esp. for real programs. In practice, a slightly
>> 'impure'
>>    halting decider may be possible.
>> 2. The counterexample P contains a function performing equivalent
>> function of H.
>>     I was thinking that if H could perform differently in different
>> implements,
>>     the HP proof won't hold (not sure of this whim). However, in real
>> situation,
>>     the 'bad instance P' should be rare (partly because it should be
>> bigger and
>>     and slower than H), real program could probably tolerate this case.
>>
>> I have not used TM since learned it. My idea of TM may have several
>> tapes or
>> 2D tapes, basicly based on my understanding of 'hard-ware', not
>> necessarily the one
>> in Linz's book. Just feel boring and thinking the opposite of the HP
>> proof.
>
> I haven't seen it mentioned (although I also can't be bothered to follow
> all of the rambling about halting in this newsgroup) but it's perfectly
> possible to prove halting for all programs in some real practical computer.
>
> Here's someone who has discovered which programs halt on a very limited
> (4-byte) computer:
>
> https://youtu.be/ym8x8B930tM
>
> You should try this method on the machine you're posting from and report
> back the results when you've finished.

Yes, it has been mentioned. In fact, you don't need the machine itself
to be limited, just that the program's state doesn't grow without bound.
When this it true, the run a second copy at half speed and check for
duplicates method will always find the non-halting machines.

That method only fails for machines that grow without bound so never
return to a previous system state.

On Friday, 8 July 2022 at 21:01:17 UTC+8, richar...@gmail.com wrote:
> On 7/8/22 8:38 AM, Mikko wrote:
> > On 2022-07-08 11:55:58 +0000, wij said:
> >
> >> On Friday, 8 July 2022 at 10:21:05 UTC+8, Jeff Barnett wrote:
> >>> On 7/7/2022 6:41 PM, Malcolm McLean wrote:
> >>>> On Thursday, 7 July 2022 at 23:59:41 UTC+1, wyni...@gmail.com wrote:
> >>>>> Do all TM running an decision algorithm give the same answer?
> >
> > Yes, all Turing machines that implement the same decision algorithm do
> > give the same answer for the same parameters. However, they may differ
> > in the required encoding of the parameters and in the presentation of
> > the result. For example, one TM may require that numbers are presented
> > as a sequence of that many *'s and another one that they are presented
> > in the usual way as a sequence of digits. And one may present the result
> > by halting in one or another of its end states whereas another one by
> > writing an Y or N to the tape.
> >
> >> 1. The HP proof demand the H a pure function.
> >
> > No. The proof only requires what the problem requires. Otherwise it
> > would not be a proof.
> >
> > The problem, as usually presented, requires that the solution is a
> > Turing machine.
> >
> > It is well known that the halting problem can be solved if the requirement
> > that the soultion be a Turing machine is sufficiently relaxed while
> > keeping the restriction that the question shall be about a Turing machine.
> > For an oracle machine with an Turing machine halting oracle can solve it.
> > However, no oracle machine can solve the halting problem of an arbitrary
> > oracle machine.
> >
> > Mikko
> >
> One key fact is that the Halt Decider MIGHT be possible if the decider
> is a more "powerful" computation structure than the things it decides,
> which means the pathological program can't be written, since it uses the
> decider, so if it can't that proof breaks.
>
> This is one of Peter's tactic, trying to define, without admitting it,
> that P can't actually use a copy of H that can be asked about P,
> sometimes because asking about P actually somehow becomes asking about
> something else.
>
> The problem thus is trying to find something more powerful than a Turing
> Machine, able to do something that a Turing Machine can't do, the
> problem being we haven't found a computation system that can do
> something that beyond what a Turing Machine can do (just do it 'faster').

I am thinking the opposite: The HP proof holds for machines equal or more powerful
than TM. For example, if 'function' is defined as executables:

#include <stdlib.h>

void P() {
if(system("H P")) for(;;){};
} int main() { P(); };

Such executable does not even need to 'know' how H is constructed.
But some detail I am still not sure of, see also another pose
https://groups.google.com/g/comp.theory/c/iGeiSuO-_oA

On 7/9/22 1:23 PM, wij wrote:
> On Friday, 8 July 2022 at 21:01:17 UTC+8, richar...@gmail.com wrote:
>> On 7/8/22 8:38 AM, Mikko wrote:
>>> On 2022-07-08 11:55:58 +0000, wij said:
>>>
>>>> On Friday, 8 July 2022 at 10:21:05 UTC+8, Jeff Barnett wrote:
>>>>> On 7/7/2022 6:41 PM, Malcolm McLean wrote:
>>>>>> On Thursday, 7 July 2022 at 23:59:41 UTC+1, wyni...@gmail.com wrote:
>>>>>>> Do all TM running an decision algorithm give the same answer?
>>>
>>> Yes, all Turing machines that implement the same decision algorithm do
>>> give the same answer for the same parameters. However, they may differ
>>> in the required encoding of the parameters and in the presentation of
>>> the result. For example, one TM may require that numbers are presented
>>> as a sequence of that many *'s and another one that they are presented
>>> in the usual way as a sequence of digits. And one may present the result
>>> by halting in one or another of its end states whereas another one by
>>> writing an Y or N to the tape.
>>>
>>>> 1. The HP proof demand the H a pure function.
>>>
>>> No. The proof only requires what the problem requires. Otherwise it
>>> would not be a proof.
>>>
>>> The problem, as usually presented, requires that the solution is a
>>> Turing machine.
>>>
>>> It is well known that the halting problem can be solved if the requirement
>>> that the soultion be a Turing machine is sufficiently relaxed while
>>> keeping the restriction that the question shall be about a Turing machine.
>>> For an oracle machine with an Turing machine halting oracle can solve it.
>>> However, no oracle machine can solve the halting problem of an arbitrary
>>> oracle machine.
>>>
>>> Mikko
>>>
>> One key fact is that the Halt Decider MIGHT be possible if the decider
>> is a more "powerful" computation structure than the things it decides,
>> which means the pathological program can't be written, since it uses the
>> decider, so if it can't that proof breaks.
>>
>> This is one of Peter's tactic, trying to define, without admitting it,
>> that P can't actually use a copy of H that can be asked about P,
>> sometimes because asking about P actually somehow becomes asking about
>> something else.
>>
>> The problem thus is trying to find something more powerful than a Turing
>> Machine, able to do something that a Turing Machine can't do, the
>> problem being we haven't found a computation system that can do
>> something that beyond what a Turing Machine can do (just do it 'faster').
>
> I am thinking the opposite: The HP proof holds for machines equal or more powerful
> than TM. For example, if 'function' is defined as executables:
>
> #include <stdlib.h>
>
> void P() {
> if(system("H P")) for(;;){};
> }
> int main() { P(); };
>
> Such executable does not even need to 'know' how H is constructed.
> But some detail I am still not sure of, see also another pose
> https://groups.google.com/g/comp.theory/c/iGeiSuO-_oA

One key fact is that there are no machines "more powerful" than a Turing
Machine that we know of. Anything that can be deterministically computed
on any computation machine we know of can be computed with a Turing
Machine, it just may scale worse, or take a lot longer.

Yes, P doesn't need to know ANY of the details about H (which is why H
being a "Simulating Halt Decider" doesn't affect the proof at all, at
least as long as a "Simulating Halt Decider" meets the minimum
requirements of being a "Halt Decider".

P just needs some way to invoke H and ask it about P(P).

The problem with Peter's decider seems to be that the input P isn't
actually allowed to properly ask H about its actual self, because
emulated calls to H are considered to be the same as actual calls to H.

The above program is also rejected because his inputs aren't allowed to
call things like system (because his emulator can't handle them).

On Saturday, 9 July 2022 at 19:45:28 UTC+1, richar...@gmail.com wrote:
> On 7/9/22 1:23 PM, wij wrote:
> > On Friday, 8 July 2022 at 21:01:17 UTC+8, richar...@gmail.com wrote:
> >> On 7/8/22 8:38 AM, Mikko wrote:
> >>> On 2022-07-08 11:55:58 +0000, wij said:
> >>>
> >>>> On Friday, 8 July 2022 at 10:21:05 UTC+8, Jeff Barnett wrote:
> >>>>> On 7/7/2022 6:41 PM, Malcolm McLean wrote:
> >>>>>> On Thursday, 7 July 2022 at 23:59:41 UTC+1, wyni...@gmail.com wrote:
> >>>>>>> Do all TM running an decision algorithm give the same answer?
> >>>
> >>> Yes, all Turing machines that implement the same decision algorithm do
> >>> give the same answer for the same parameters. However, they may differ
> >>> in the required encoding of the parameters and in the presentation of
> >>> the result. For example, one TM may require that numbers are presented
> >>> as a sequence of that many *'s and another one that they are presented
> >>> in the usual way as a sequence of digits. And one may present the result
> >>> by halting in one or another of its end states whereas another one by
> >>> writing an Y or N to the tape.
> >>>
> >>>> 1. The HP proof demand the H a pure function.
> >>>
> >>> No. The proof only requires what the problem requires. Otherwise it
> >>> would not be a proof.
> >>>
> >>> The problem, as usually presented, requires that the solution is a
> >>> Turing machine.
> >>>
> >>> It is well known that the halting problem can be solved if the requirement
> >>> that the soultion be a Turing machine is sufficiently relaxed while
> >>> keeping the restriction that the question shall be about a Turing machine.
> >>> For an oracle machine with an Turing machine halting oracle can solve it.
> >>> However, no oracle machine can solve the halting problem of an arbitrary
> >>> oracle machine.
> >>>
> >>> Mikko
> >>>
> >> One key fact is that the Halt Decider MIGHT be possible if the decider
> >> is a more "powerful" computation structure than the things it decides,
> >> which means the pathological program can't be written, since it uses the
> >> decider, so if it can't that proof breaks.
> >>
> >> This is one of Peter's tactic, trying to define, without admitting it,
> >> that P can't actually use a copy of H that can be asked about P,
> >> sometimes because asking about P actually somehow becomes asking about
> >> something else.
> >>
> >> The problem thus is trying to find something more powerful than a Turing
> >> Machine, able to do something that a Turing Machine can't do, the
> >> problem being we haven't found a computation system that can do
> >> something that beyond what a Turing Machine can do (just do it 'faster').
> >
> > I am thinking the opposite: The HP proof holds for machines equal or more powerful
> > than TM. For example, if 'function' is defined as executables:
> >
> > #include <stdlib.h>
> >
> > void P() {
> > if(system("H P")) for(;;){};
> > }
> > int main() { P(); };
> >
> > Such executable does not even need to 'know' how H is constructed.
> > But some detail I am still not sure of, see also another pose
> > https://groups.google.com/g/comp.theory/c/iGeiSuO-_oA
> One key fact is that there are no machines "more powerful" than a Turing
> Machine that we know of. Anything that can be deterministically computed
> on any computation machine we know of can be computed with a Turing
> Machine, it just may scale worse, or take a lot longer.
>
Humans seem to be able to do things that Turing machines can't. So it's
possible that the Turing machine isn't the last word in symbol processing.
However we don't understand the basic principles on which a machine capable
of learning a natural language, for instance, would work on.

On 7/9/22 3:21 PM, Malcolm McLean wrote:
> On Saturday, 9 July 2022 at 19:45:28 UTC+1, richar...@gmail.com wrote:
>> On 7/9/22 1:23 PM, wij wrote:
>>> On Friday, 8 July 2022 at 21:01:17 UTC+8, richar...@gmail.com wrote:
>>>> On 7/8/22 8:38 AM, Mikko wrote:
>>>>> On 2022-07-08 11:55:58 +0000, wij said:
>>>>>
>>>>>> On Friday, 8 July 2022 at 10:21:05 UTC+8, Jeff Barnett wrote:
>>>>>>> On 7/7/2022 6:41 PM, Malcolm McLean wrote:
>>>>>>>> On Thursday, 7 July 2022 at 23:59:41 UTC+1, wyni...@gmail.com wrote:
>>>>>>>>> Do all TM running an decision algorithm give the same answer?
>>>>>
>>>>> Yes, all Turing machines that implement the same decision algorithm do
>>>>> give the same answer for the same parameters. However, they may differ
>>>>> in the required encoding of the parameters and in the presentation of
>>>>> the result. For example, one TM may require that numbers are presented
>>>>> as a sequence of that many *'s and another one that they are presented
>>>>> in the usual way as a sequence of digits. And one may present the result
>>>>> by halting in one or another of its end states whereas another one by
>>>>> writing an Y or N to the tape.
>>>>>
>>>>>> 1. The HP proof demand the H a pure function.
>>>>>
>>>>> No. The proof only requires what the problem requires. Otherwise it
>>>>> would not be a proof.
>>>>>
>>>>> The problem, as usually presented, requires that the solution is a
>>>>> Turing machine.
>>>>>
>>>>> It is well known that the halting problem can be solved if the requirement
>>>>> that the soultion be a Turing machine is sufficiently relaxed while
>>>>> keeping the restriction that the question shall be about a Turing machine.
>>>>> For an oracle machine with an Turing machine halting oracle can solve it.
>>>>> However, no oracle machine can solve the halting problem of an arbitrary
>>>>> oracle machine.
>>>>>
>>>>> Mikko
>>>>>
>>>> One key fact is that the Halt Decider MIGHT be possible if the decider
>>>> is a more "powerful" computation structure than the things it decides,
>>>> which means the pathological program can't be written, since it uses the
>>>> decider, so if it can't that proof breaks.
>>>>
>>>> This is one of Peter's tactic, trying to define, without admitting it,
>>>> that P can't actually use a copy of H that can be asked about P,
>>>> sometimes because asking about P actually somehow becomes asking about
>>>> something else.
>>>>
>>>> The problem thus is trying to find something more powerful than a Turing
>>>> Machine, able to do something that a Turing Machine can't do, the
>>>> problem being we haven't found a computation system that can do
>>>> something that beyond what a Turing Machine can do (just do it 'faster').
>>>
>>> I am thinking the opposite: The HP proof holds for machines equal or more powerful
>>> than TM. For example, if 'function' is defined as executables:
>>>
>>> #include <stdlib.h>
>>>
>>> void P() {
>>> if(system("H P")) for(;;){};
>>> }
>>> int main() { P(); };
>>>
>>> Such executable does not even need to 'know' how H is constructed.
>>> But some detail I am still not sure of, see also another pose
>>> https://groups.google.com/g/comp.theory/c/iGeiSuO-_oA
>> One key fact is that there are no machines "more powerful" than a Turing
>> Machine that we know of. Anything that can be deterministically computed
>> on any computation machine we know of can be computed with a Turing
>> Machine, it just may scale worse, or take a lot longer.
>>
> Humans seem to be able to do things that Turing machines can't. So it's
> possible that the Turing machine isn't the last word in symbol processing.
> However we don't understand the basic principles on which a machine capable
> of learning a natural language, for instance, would work on.

I think part of this is that Human processing isn't restricted to strict
deterministic paths as Computations are defined on. Non-deterministic
computation models are still (as far as I know) still in their infancy,
and in a major sense the "Halting Problem" needs major work to reframe
in non-deterministic computation model, since you get other
possibilities besides will halt in a finite time or will never halt,
since it might be the answer is it halts or not with some probability,
or the probability that it hasn't halted decreases over time, to some
limit (perhaps zero), so perhaps we can be assured that the machine WILL
halt, but there is no upper bound on how long it might take.

It also seems to work on a massively parallel basis that is hard to
build hardware analogs of.

On 09/07/2022 20:21, Malcolm McLean wrote:
> Humans seem to be able to do things that Turing machines can't.

Well, of course. We can sing and dance, cook, go to parties,
etc., etc. But in terms of effective computations, not so much. We're
in Church-Turing territory. AFAIK, there is no evidence at all that
things we could [eg] imagine robots being programmed to do differ in
any interesting [visible] way from the things humans do; but it all
depends on your view of the Chinese Room [thought] experiment. None
of that is relevant to the things usually being discussed here; there
is no evidence [none, nil, nada] that the standard theory of the HP is
in any way wrong. People who nevertheless waste their time trying to
construct halt deciders [or near equivalents thereto] are barking at
the moon. Nothing to see here, move along.

--
Andy Walker, Nottingham.
Andy's music pages: www.cuboid.me.uk/andy/Music
Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Balakirev

Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:

> Humans seem to be able to do things that Turing machines can't. So it's
> possible that the Turing machine isn't the last word in symbol
> processing.

What sort of thing are you thinking of here?

--
Ben.

On 7/9/2022 3:40 PM, Ben Bacarisse wrote:
> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>
>> Humans seem to be able to do things that Turing machines can't. So it's
>> possible that the Turing machine isn't the last word in symbol
>> processing.
>
> What sort of thing are you thinking of here?
Well there is an old chestnut that we are all aware of: A class of
augmented TM that includes an Oracle that functions as a Halt Decider
when a delimited area of its tape contains the representations of an
ordinary TM and an input string for it. Of course that class of TM,
while being able to solve the ordinary TM halting problem, does not
contain a halting decider for its own augmented class. And this leads to
a theorem about an infinite hierarchy of stronger and stronger machine
classes that cannot solve HP for their own class.

As for humans, one must not make the POOP mistake, i.e., that is miss
the fact that a purported Decider (of anything) includes all those
states of things and phenomena that influence its behavior. Even if some
of these things are random (random usually means stochastic when we
don't know the explicit behavior distribution) there are TM classes that
will make similar calculations and exhibit similar behaviors as we learn
more about measures of the underlying stochastic processes.

In other words, I believe that humans are not theoretically very
different from formal machines; rather, the amount of the environment
that affects us is much broader. And this brings us to the topic of
(Herb) Simon's ant: We watch an ant traveling a very complicated and
interesting path on the beach. The complexity makes us assume that the
ant must be using intelligence to control its behavior. But, of course,
there is a radically different explanation possible - the ant is using
some very simple and primitive responses to its environment and the
environment is very complex therefore, so is the ant's observed behavior.

To complete our ant example. Assume that the ant is heading in some
particular direction and when there is an elevation change, the ant
adjusts its course to travel less distance or use less energy. Put your
eyes close to the sand and observe how hilly it is from an ant's point
of view. That 0.1" "wave" in the sand is quite large to an ant even
though you and I don't notice it at all.

There is also another consideration: when folks start compare humans and
computers, they compare computers to the very best and brightest humans.
By the same considerations, 99.99 percent of humans lose the comparison,
not just the machines. Example: Chess used to be considered a sign of
intelligence - anybody who played a good game was smart! People laughed
when in the 1950s Newell and Simon said that computers would play world
champion class chess in 10 years. Well the 10 years was off by a bunch
but by the mid 1990s those laughing changed their tune to "Computers win
by brute force and that isn't a sign of intelligence."! Since these same
folks didn't (and still don't) know how world champions decide moves it
may be that humans aren't any more intelligent than the machines. At the
present state of computer chess where computers hold their own against
just about everyone, the critics are chagrin.

One last comment is that computer chess wasn't only good because of
brute force; Rather the first really decent programs and hardware was
built at CMU by Hans Berliner and his students. It was these students
who, after graduating, went to IBM and other places that were willing to
invest in serious hardware - Hans had few grants for chess at CMU and
made arranged to "borrow" stuff from programs that were much better funded.

The point was that Hans for many years was either the World Postal Chess
Champion. That meant that he was one of the handful of best chess
players in the world if he was given a few hours to make a move. His
knowledge of chess as well as AI style search algorithms and most of
serious computer science made him ideal to conduct this research. Until
he started this project seriously, those building chess hardware made
the special stuff whizz through the look ahead search.

Hans decided to do it differently: he concentrated the special hardware
to do extensive position evaluation at the end of the searches - he knew
he and other chess masters spent most of their mental energies there. So
it was his knowledge of what was important that led him take a quantum
jump in chess technology. So the modern chess programs that play at
grand master level are really doing it using knowledge not just brute force.

Phooey on the doubters. We gave humans too much credit by far. Hell, a
lot of people are dumb enough to believe that we were made in God's
image and that we possess quality (rather than quantitative) advantages
over the animals. Don't you believe it until you've met and spent time
with lots and lots of people. And make sure that half of them appear to
be at or less than average intelligence and the other half can be those
who you normally interact with. (I have no idea how to measure
intelligence and that's why I suggest meeting lots of people.) Or more
simply, walk out your front door and take a good breath and when you
quit coughing try to figure how we could be so dumb to destroy the
planet. Kurt Vonnegut has opined that the Earth's immune system is
trying to kill off the human race to protect itself.
--
Jeff Barnett

On Sunday, 10 July 2022 at 07:47:13 UTC+1, Jeff Barnett wrote:
>
> In other words, I believe that humans are not theoretically very
> different from formal machines; rather, the amount of the environment
> that affects us is much broader. And this brings us to the topic of
> (Herb) Simon's ant: We watch an ant traveling a very complicated and
> interesting path on the beach. The complexity makes us assume that the
> ant must be using intelligence to control its behavior. But, of course,
> there is a radically different explanation possible - the ant is using
> some very simple and primitive responses to its environment and the
> environment is very complex therefore, so is the ant's observed behavior.
>
> To complete our ant example. Assume that the ant is heading in some
> particular direction and when there is an elevation change, the ant
> adjusts its course to travel less distance or use less energy. Put your
> eyes close to the sand and observe how hilly it is from an ant's point
> of view. That 0.1" "wave" in the sand is quite large to an ant even
> though you and I don't notice it at all.
>
Ants placed in a new environment initially fan out at random, laying a pheromone
trail as they go. When they find food, they pick it, and do an about turn, following
the trail back to the nest. Follow up ants then apply a stochastic algorithm -
they follow the pheremone trail, but with some probability of a deviation. They
also lay trails as they go.
As time goes on, the short routes to food sources get stronger and stronger pheromone
trails attached to them, with more and more ants adhering to them. So it looks like
the ants are intelligently route finding. In fact it's emergent behaviour from a few
simple rules.

But it's not at all clear that this type of rule underlies human behaviour, with neurons
taking the role of ants. It may be the case, but no one has proposed a workable
model that stands up (I think, I haven't exhaustively reviewed the literature,
though I keep an interest in this sort of thing. I'm a biologist by training).

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> Malcolm McLean <malcolm.arthur.mclean@gmail.com> writes:
>
>> Humans seem to be able to do things that Turing machines can't. So it's
>> possible that the Turing machine isn't the last word in symbol
>> processing.
>
> What sort of thing are you thinking of here?

Jeff's reply may a derailed things. I really did want to know what sort
of human symbol processing you were thinking of here. I'm sure we'll
disagree but, as always, I'm curious about what facts led to you making
that statement.

--
Ben.

On Sunday, 10 July 2022 at 04:21:34 UTC+8, Andy Walker wrote:
> On 09/07/2022 20:21, Malcolm McLean wrote:
> > Humans seem to be able to do things that Turing machines can't.
> Well, of course. We can sing and dance, cook, go to parties,
> etc., etc. But in terms of effective computations, not so much. We're
> in Church-Turing territory. AFAIK, there is no evidence at all that
> things we could [eg] imagine robots being programmed to do differ in
> any interesting [visible] way from the things humans do; but it all
> depends on your view of the Chinese Room [thought] experiment. None
> of that is relevant to the things usually being discussed here; there
> is no evidence [none, nil, nada] that the standard theory of the HP is
> in any way wrong. People who nevertheless waste their time trying to
> construct halt deciders [or near equivalents thereto] are barking at
> the moon. Nothing to see here, move along.
> --
> Andy Walker, Nottingham.
> Andy's music pages: www.cuboid.me.uk/andy/Music
> Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Balakirev

The sentence "No halt decider exists" may be misleading without further
understanding (Bacon classified as knowledge of/from market place, theater...).
The HP proof only proves in its definition. It does not rule out a H (in its definition)
of 99.999...% accuracy, which is desirable in practice. In theory, well, that depends.
People learning by rote (most knowledge is hear and say, school, the education
system?) usually has such synoptic tendency that we all have, more or less.
(like the 0.999... problem and infinity, seems only I understand more,:-))

On 10/07/2022 13:55, wij wrote:

> The HP proof only proves in its definition. It does not rule out a H (in its definition)
> of 99.999...% accuracy, which is desirable in practice. In theory, well, that depends.

"Everyone" knows that there are useful partial halt deciders. After that,
it depends on what you mean. What is that "99.999...% accuracy"? Getting the
answer wrong is different from giving up with "don't know". What is "99.999...%"
a percentage /of/? If of all possible programs, then you need perhaps to
consider that "almost all" programs are more than 10000000000 lines long, almost
all contain somewhere the sequence "here: goto here;" or moral equivalent, or
indeed any proposed "pathological" [in the PO sense] code, .... It's not a
useful metric in practice. If you mean 99.999...% of currently-written real-
life code, then yes, that could obviously be useful in practice; OTOH, /good/
real-life code comes with assertions and other guarantees that /prove/ the
quality of the program, and that's much more useful, so your 99.999...% might
turn out to be 100% of well-written code, but a much lower percentage of the
code written by third-rate programmers, or even by expert programmers writing
non-critical [eg, exploratory] applications.

As for theory, as you indicate, that's another matter. Consider, for
example, that almost all integers are composite; that doesn't stop primes
from being interesting, and even useful.

> People learning by rote (most knowledge is hear and say, school, the education
> system?) usually has such synoptic tendency that we all have, more or less.

That is, to a significant extent, a function of the society to which
people belong. Some parts of the world are much more "compliant" than others.
But those who make significant contributions to knowledge have not come by
those contributions by rote learning. Every academic here will have come
across students, even postgraduates, whose only interest is passing the exam,
who just want to know what "the answer" is, and who get very frustrated if
told to go away and find how things work. The joy comes from finding the
student who wants to learn, not by rote, but by study and debate; and that
is where the Nobel prize and Fields medal winners come from.

> (like the 0.999... problem and infinity, seems only I understand more,:-))

No, you have an eccentric view and do not understand the background
which makes it eccentric. No-one objects to you inventing some new maths,
but you need to understand how it fits with conventional maths [if at all].
Not all convention comes from rote.

--
Andy Walker, Nottingham.
Andy's music pages: www.cuboid.me.uk/andy/Music
Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Dunhill

On Sunday, 10 July 2022 at 23:40:21 UTC+8, Andy Walker wrote:
> On 10/07/2022 13:55, wij wrote:
>
> > The HP proof only proves in its definition. It does not rule out a H (in its definition)
> > of 99.999...% accuracy, which is desirable in practice. In theory, well, that depends.
> "Everyone" knows that there are useful partial halt deciders. After that,
> it depends on what you mean. What is that "99.999...% accuracy"? Getting the
> answer wrong is different from giving up with "don't know". What is "99.999...%"
> a percentage /of/? If of all possible programs, then you need perhaps to
> consider that "almost all" programs are more than 10000000000 lines long, almost
> all contain somewhere the sequence "here: goto here;" or moral equivalent, or
> indeed any proposed "pathological" [in the PO sense] code, .... It's not a
> useful metric in practice. If you mean 99.999...% of currently-written real-
> life code, then yes, that could obviously be useful in practice; OTOH, /good/
> real-life code comes with assertions and other guarantees that /prove/ the
> quality of the program, and that's much more useful, so your 99.999...% might
> turn out to be 100% of well-written code, but a much lower percentage of the
> code written by third-rate programmers, or even by expert programmers writing
> non-critical [eg, exploratory] applications.

For instance, I don't really understand what Steven Paul Jobs said and in the
provided https://youtu.be/ym8x8B930tM
However, the idea is possible a good halt decider could exist that makes the bad
instance P has to be so big to exceed what the real platform allow, or something
like this.

> As for theory, as you indicate, that's another matter. Consider, for
> example, that almost all integers are composite; that doesn't stop primes
> from being interesting, and even useful.
> > People learning by rote (most knowledge is hear and say, school, the education
> > system?) usually has such synoptic tendency that we all have, more or less.
> That is, to a significant extent, a function of the society to which
> people belong. Some parts of the world are much more "compliant" than others.
> But those who make significant contributions to knowledge have not come by
> those contributions by rote learning. Every academic here will have come
> across students, even postgraduates, whose only interest is passing the exam,
> who just want to know what "the answer" is, and who get very frustrated if
> told to go away and find how things work. The joy comes from finding the
> student who wants to learn, not by rote, but by study and debate; and that
> is where the Nobel prize and Fields medal winners come from.

I just highlight some points to ponder about, difficult to have a clear subject.
My English is not good enough to talk the phenomenon I saw without getting confused.

> > (like the 0.999... problem and infinity, seems only I understand more,:-))
> No, you have an eccentric view and do not understand the background
> which makes it eccentric. No-one objects to you inventing some new maths,
> but you need to understand how it fits with conventional maths [if at all].
> Not all convention comes from rote.

My eccentric math. is improving everyday (not in a hurry to develop it) while
you standstill with only 'eccentric' in mind. (e.g. several paradoxes involving
infinity were no longer paradoxical to me, like 0.999..., Zeno's paradox, super-
task,...). Why am I not eccentric? Because I use computer, everything is very
clear. I 'found' (still working on) large (or main) portion of math. CAN and
SHOULD be based/explained by ideas developed in CS.
Using 'conventional maths' to develop CS?

> --
> Andy Walker, Nottingham.
> Andy's music pages: www.cuboid.me.uk/andy/Music
> Composer of the day: www.cuboid.me.uk/andy/Music/Composers/Dunhill

>
> For instance, I don't really understand what Steven Paul Jobs said and in the
> provided https://youtu.be/ym8x8B930tM
> However, the idea is possible a good halt decider could exist that makes the bad
> instance P has to be so big to exceed what the real platform allow, or something
> like this.
>

Sorry if my comment was of little help. The video I shared is a
submission to SIGBOVIK. SIGBOVIK is a special interest group for people
who spend all day thinking about halt deciders. Perhaps you could submit
a paper for next year.

On Monday, 11 July 2022 at 06:10:10 UTC+8, Steven Paul Jobs wrote:
> >
> > For instance, I don't really understand what Steven Paul Jobs said and in the
> > provided https://youtu.be/ym8x8B930tM
> > However, the idea is possible a good halt decider could exist that makes the bad
> > instance P has to be so big to exceed what the real platform allow, or something
> > like this.
> >
> Sorry if my comment was of little help. The video I shared is a
> submission to SIGBOVIK. SIGBOVIK is a special interest group for people
> who spend all day thinking about halt deciders. Perhaps you could submit
> a paper for next year.

I was focusing on refuting "halt decider is impossible" from the stereotype
caused by the HP Proof. It may be over-stressed for people to think halt decider
is possible (there are many ways possible depending on its definition), but should
be OK if it could make people think harder.
Thanks for the reply, I cannot comment the 4-bytes decider.