From Newsgroup: sci.logic

On 6/6/2004 9:11 AM, Peter Olcott wrote:

One very simple transformation of the problem into a solvable problem
is to convert the Boolean function DoesItHalt() into a tertiary response: True, False, Neither.

if (DoesItHalt() == True)
while(True) // loop forever
;
else if (DoesItHalt() == False)
return False;

else if (DoesItHalt() == NeitherTrueNorFalse)
return NeitherTrueNorFalse;

So the original Halting Problem was incorrectly formed specifically
because it was framed as a Boolean function, thus failing to account
for possible inputs that result in a reply other than True or False.

--
Copyright 2024 Olcott

"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: sci.logic

On 8/24/2025 4:56 PM, olcott wrote:

On 6/6/2004 9:11 AM, Peter Olcott wrote:

One very simple transformation of the problem into a solvable problem
is to convert the Boolean function DoesItHalt() into a tertiary response:
True, False, Neither.

if (DoesItHalt() == True)
-a-a while(True)-a-a // loop forever
-a-a-a-a ;
else if (DoesItHalt() == False)
-a-a return False;

else if-a (DoesItHalt() == NeitherTrueNorFalse)
-a-a return NeitherTrueNorFalse;

So the original Halting Problem was incorrectly formed specifically
because it was framed as a Boolean function, thus failing to account
for possible inputs that result in a reply other than True or False.

https://www.usenetarchives.com/view.php?id=sci.logic&mid=PGJDRndjLjEzOTgwJEd4NC4yNTM3QGJndG5zYzA0LW5ld3Mub3BzLndvcmxkbmV0LmF0dC5uZXQ%2B
--
Copyright 2025 Olcott "Talent hits a target no one else can hit; Genius
hits a target no one else can see." Arthur Schopenhauer
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: sci.logic


On the bright side, 500 more posts and we
will have 2030. But then there will be a
lready Artificial General intelligence (AGI),
which will answer all your questions in a blink.
Relieving the community from all pain and headaches.

We say that the hour of discovery cannot be
forecast, but when we say this, we imagine
that the hour is placed in an obscure and
distant future. Never occurs to us that it has
any relation to today. This day, or any day,
could be the event.

Sometimes discovery comes in circles, shows
us the dark hand of completely forgetting we
each must eventually clasp. Nothing is more
difficult than the loss of past knowledge,
especially when it is our own end
and AGI takes over.

~~ Eulogy in Final Destination, Flight 180 Crash

Mild Shock schrieb:

Hi,

Lee NaishrCOs idea for an infinite tree syntax:

/* Lee NaishrCOs idea */
naish(X, Y) :-
-a-a naish([], X, Y).

naish(S, X, Y) :- compound(X),
-a-a member(Z-Y, S), X == Z, !.
naish(S, X, Y) :- compound(X), !,
-a-a length(S, N),
-a-a X =.. [F|L],
-a-a maplist(naish([X-'$IDX'(N)|S]), L, R),
-a-a Y =.. [F|R].
naish(_, X, X).

Now define a compare:

naish_compare(C, X, Y) :-
-a-a naish(X, A),
-a-a naish(Y, B),
-a-a compare(C, A, B).

Works fine on this example:

?- X = s(s(1,Y),0), Y = s(s(1,X),1),
-a-a naish_compare(C, X, Y).
C = (>).

The residual problem is, that it is extremly
slow. Much slower than the native compare/3
which doesnrCOt use a stack, but a Union Find

structure. So conceptually total order and
natural order compare/3 are easy, the hard
part is making them ultra fast!

Bye

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: sci.logic


On the bright side, 500 more posts and we
will have 2030. But then there will be a
lready Artificial General intelligence (AGI),
which will answer all your questions in a blink.
Relieving the community from all pain and headaches.

We say that the hour of discovery cannot be
forecast, but when we say this, we imagine
that the hour is placed in an obscure and
distant future. Never occurs to us that it has
any relation to today. This day, or any day,
could be the event.

Sometimes discovery comes in circles, shows
us the dark hand of completely forgetting we
each must eventually clasp. Nothing is more
difficult than the loss of past knowledge,
especially when it is our own end
and AGI takes over.

~~ Eulogy in Final Destination, Flight 180 Crash

Mild Shock schrieb:

Hi,

Lee NaishrCOs idea for an infinite tree syntax:

/* Lee NaishrCOs idea */
naish(X, Y) :-
-a-a naish([], X, Y).

naish(S, X, Y) :- compound(X),
-a-a member(Z-Y, S), X == Z, !.
naish(S, X, Y) :- compound(X), !,
-a-a length(S, N),
-a-a X =.. [F|L],
-a-a maplist(naish([X-'$IDX'(N)|S]), L, R),
-a-a Y =.. [F|R].
naish(_, X, X).

Now define a compare:

naish_compare(C, X, Y) :-
-a-a naish(X, A),
-a-a naish(Y, B),
-a-a compare(C, A, B).

Works fine on this example:

?- X = s(s(1,Y),0), Y = s(s(1,X),1),
-a-a naish_compare(C, X, Y).
C = (>).

The residual problem is, that it is extremly
slow. Much slower than the native compare/3
which doesnrCOt use a stack, but a Union Find

structure. So conceptually total order and
natural order compare/3 are easy, the hard
part is making them ultra fast!

Bye

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: sci.logic

Hi,

Now this might come as a shock for this french
philosopher, who had that much problems with
Tennant's logical system called TROLL LOGIC.

Or was it core logic. Don't remember anymore:

Representation based comparison does seem to
work well on everything IrCOve tested, e.g.,
rCLMonkey testrCY for transitivity and anti-symmetry
with repeat counts of 10,000,000.

Well there is balance between testing and proving
in computer science. You could say there is balance
between Inductive and Deductive science.

https://de.wikipedia.org/wiki/Induktion_(Philosophie)

You donrCOt need to test transitivity. You can
prove it! Mathematicians usually simply say
if < is a total order, then <rC# is a total order:

Theorem on Order Homomorphism

Proof:
Given rep:RraAH, then define x<rC#y:rf|rep(x)<rep(y).
If rep is injective, then <rC# is transitive
and anti-symmetric.

Assume towards a contradiction that <rC# is not
anti-symmetric. Then we would have x,y such
that x<rC#yreoxreayreo-4x<rC#y. By definition of <rC# and
injectivity of rep we would have rep(x)<rep(y)
reorep(x)rearep(y)reo-4rep(x)<rep(y). A contradiction
with < being anti-symmetric.

Assume towards a contradiction that <rC# is
not transitive. Then we would have x,y,z such
that x<rC#yreoy<rC#zreo-4x<rC#z. By definition of <rC# we
would have rep(x)<rep(y)reorep(y)<rep(z)reo
-4rep(x)<rep(z). A contradiction with <
being transitive.

Q.E.D.

Bye

Mild Shock schrieb:

On the bright side, 500 more posts and we
will have 2030. But then there will be a
lready Artificial General intelligence (AGI),
which will answer all your questions in a blink.
Relieving the community from all pain and headaches.

We say that the hour of discovery cannot be
forecast, but when we say this, we imagine
that the hour is placed in an obscure and
distant future. Never occurs to us that it has
any relation to today. This day, or any day,
could be the event.

Sometimes discovery comes in circles, shows
us the dark hand of completely forgetting we
each must eventually clasp. Nothing is more
difficult than the loss of past knowledge,
especially when it is our own end
and AGI takes over.

~~ Eulogy in Final Destination, Flight 180 Crash

Mild Shock schrieb:

Hi,

Lee NaishrCOs idea for an infinite tree syntax:

/* Lee NaishrCOs idea */
naish(X, Y) :-
-a-a-a naish([], X, Y).

naish(S, X, Y) :- compound(X),
-a-a-a member(Z-Y, S), X == Z, !.
naish(S, X, Y) :- compound(X), !,
-a-a-a length(S, N),
-a-a-a X =.. [F|L],
-a-a-a maplist(naish([X-'$IDX'(N)|S]), L, R),
-a-a-a Y =.. [F|R].
naish(_, X, X).

Now define a compare:

naish_compare(C, X, Y) :-
-a-a-a naish(X, A),
-a-a-a naish(Y, B),
-a-a-a compare(C, A, B).

Works fine on this example:

?- X = s(s(1,Y),0), Y = s(s(1,X),1),
-a-a-a naish_compare(C, X, Y).
C = (>).

The residual problem is, that it is extremly
slow. Much slower than the native compare/3
which doesnrCOt use a stack, but a Union Find

structure. So conceptually total order and
natural order compare/3 are easy, the hard
part is making them ultra fast!

Bye

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: sci.logic


Hi,

I hope @kuniaki.mukai will like this post.
Now that we are past this generic type of
compare/3, where rep/2 is some representation:

rep_compare(C, X, Y) :-
rep(X, A),
rep(Y, B),
compare(C, A, B).

We can now switch gears, and leave naish/2
behind us, and turn to Deutsch-Schorr-Waite
marking algorithm, that can give us as well
a numbering of cycle nodes:

deutsch(X, Y) :-
deutsch(X, Y, [], _).

deutsch(X, V, S, S) :- compound(X),
member(v(Z,T,Y,W), S), X == Z, !,
(var(T) -> V = Y; V = T),
W = 1.
deutsch(X, Y, S, T) :- compound(X), !,
length(S, N),
X =.. [F|L],
foldl(deutsch, L, R, [v(X,V,'$IDX'(N),W)|S], T),
Y =.. [F|R],
(var(W) -> V = Y; V = '$IDX'(N)).
deutsch(X, X, S, S).

The Schorr-Waite graph marking algorithm appeared
first in about 1968; it is also attributed to
Peter Deutsch. So I am calling the above predicate
deutsch/2 because it is a shorter name then

schorr_waite/2 or deutsch_schorr_waite/3.

Bye

Mild Shock schrieb:

Hi,

Now this might come as a shock for this french
philosopher, who had that much problems with
Tennant's logical system called TROLL LOGIC.

Or was it core logic. Don't remember anymore:

Representation based comparison does seem to
work well on everything IrCOve tested, e.g.,
rCLMonkey testrCY for transitivity and anti-symmetry
with repeat counts of 10,000,000.

Well there is balance between testing and proving
in computer science. You could say there is balance
between Inductive and Deductive science.

https://de.wikipedia.org/wiki/Induktion_(Philosophie)

You donrCOt need to test transitivity. You can
prove it! Mathematicians usually simply say
if < is a total order, then <rC# is a total order:

-a-a-a Theorem on Order Homomorphism

-a-a-a Proof:
-a-a-a Given rep:RraAH, then define x<rC#y:rf|rep(x)<rep(y).
-a-a-a If rep is injective, then <rC# is transitive
-a-a-a and anti-symmetric.

-a-a-a Assume towards a contradiction that <rC# is not
-a-a-a anti-symmetric. Then we would have x,y such
-a-a-a that x<rC#yreoxreayreo-4x<rC#y. By definition of <rC# and
-a-a-a injectivity of rep we would have rep(x)<rep(y)
-a-a-a reorep(x)rearep(y)reo-4rep(x)<rep(y). A contradiction
-a-a-a with < being anti-symmetric.

-a-a-a Assume towards a contradiction that <rC# is
-a-a-a not transitive. Then we would have x,y,z such
-a-a-a that x<rC#yreoy<rC#zreo-4x<rC#z. By definition of <rC# we
-a-a-a would have rep(x)<rep(y)reorep(y)<rep(z)reo
-a-a-a -4rep(x)<rep(z). A contradiction with <
-a-a-a being transitive.

-a-a-a Q.E.D.

Bye

Mild Shock schrieb:

On the bright side, 500 more posts and we
will have 2030. But then there will be a
lready Artificial General intelligence (AGI),
which will answer all your questions in a blink.
Relieving the community from all pain and headaches.

We say that the hour of discovery cannot be
forecast, but when we say this, we imagine
that the hour is placed in an obscure and
distant future. Never occurs to us that it has
any relation to today. This day, or any day,
could be the event.

Sometimes discovery comes in circles, shows
us the dark hand of completely forgetting we
each must eventually clasp. Nothing is more
difficult than the loss of past knowledge,
especially when it is our own end
and AGI takes over.

~~ Eulogy in Final Destination, Flight 180 Crash

Mild Shock schrieb:

Hi,

Lee NaishrCOs idea for an infinite tree syntax:

/* Lee NaishrCOs idea */
naish(X, Y) :-
-a-a-a naish([], X, Y).

naish(S, X, Y) :- compound(X),
-a-a-a member(Z-Y, S), X == Z, !.
naish(S, X, Y) :- compound(X), !,
-a-a-a length(S, N),
-a-a-a X =.. [F|L],
-a-a-a maplist(naish([X-'$IDX'(N)|S]), L, R),
-a-a-a Y =.. [F|R].
naish(_, X, X).

Now define a compare:

naish_compare(C, X, Y) :-
-a-a-a naish(X, A),
-a-a-a naish(Y, B),
-a-a-a compare(C, A, B).

Works fine on this example:

?- X = s(s(1,Y),0), Y = s(s(1,X),1),
-a-a-a naish_compare(C, X, Y).
C = (>).

The residual problem is, that it is extremly
slow. Much slower than the native compare/3
which doesnrCOt use a stack, but a Union Find

structure. So conceptually total order and
natural order compare/3 are easy, the hard
part is making them ultra fast!

Bye

--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: sci.logic


Hi,

What can it do? Well it detects sharing and
is thus more resilient to examples such as hydra/2.

Naish has no sharing detection:

?- X = f(g(h(Z))), Y = k(X,X), naish(Y, T).
T = k(f(g(h(Z))), f(g(h(Z)))).

?- X = f(g(h(X))), Y = k(X,X), naish(Y, T).
T = k(f(g(h('$IDX'(1)))), f(g(h('$IDX'(1))))).

Deutsch has sharing detection:

?- X = f(g(h(Z))), Y = k(X,X), deutsch(Y, T).
T = k(f(g(h(Z))), f(g(h(Z)))).

?- X = f(g(h(X))), Y = k(X,X), deutsch(Y, T).
T = k(f(g(h('$IDX'(1)))), '$IDX'(1)).

You can also inspect the results with
'$factorize_term'/3, to see sharing that is
not shown in the top-level. This gives yet
another compare/3 which is a total order

and which is conservative and can deal
with sharing, when combined with the
SWI-Prolog compare/3 in a rep_compare/3.
But still expensive, not for pratical

use, only for educational use.

Bye

Mild Shock schrieb:

Hi,

I hope @kuniaki.mukai will like this post.
Now that we are past this generic type of
compare/3, where rep/2 is some representation:

rep_compare(C, X, Y) :-
-a-a-a rep(X, A),
-a-a-a rep(Y, B),
-a-a-a compare(C, A, B).

We can now switch gears, and leave naish/2
behind us, and turn to Deutsch-Schorr-Waite
marking algorithm, that can give us as well
a numbering of cycle nodes:

deutsch(X, Y) :-
-a-a deutsch(X, Y, [], _).

deutsch(X, V, S, S) :- compound(X),
-a-a member(v(Z,T,Y,W), S), X == Z, !,
-a-a (var(T) -> V = Y; V = T),
-a-a W = 1.
deutsch(X, Y, S, T) :- compound(X), !,
-a-a length(S, N),
-a-a X =.. [F|L],
-a-a foldl(deutsch, L, R, [v(X,V,'$IDX'(N),W)|S], T),
-a-a Y =.. [F|R],
-a-a (var(W) -> V = Y; V = '$IDX'(N)).
deutsch(X, X, S, S).

The Schorr-Waite graph marking algorithm appeared
first in about 1968; it is also attributed to
Peter Deutsch. So I am calling the above predicate
deutsch/2 because it is a shorter name then

schorr_waite/2 or deutsch_schorr_waite/3.

Bye

--- Synchronet 3.21a-Linux NewsLink 1.2