From Newsgroup: sci.math


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.math

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
--- Synchronet 3.21a-Linux NewsLink 1.2

From Newsgroup: sci.math

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