Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.prolog > #14808

Switching Gears: From Lee Naish to Peter Deutsch (Was: Reflect on Sience not Frog Legs)

Show all headers | View raw

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, an 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 I’ve tested, e.g.,
>  > “Monkey test” 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 don’t need to test transitivity. You can
> prove it! Mathematicians usually simply say
> if < is a total order, then <′ is a total order:
> 
>      Theorem on Order Homomorphism
> 
>      Proof:
>      Given rep:R→H, then define x<′y:⟺rep(x)<rep(y).
>      If rep is injective, then <′ is transitive
>      and anti-symmetric.
> 
>      Assume towards a contradiction that <′ is not
>      anti-symmetric. Then we would have x,y such
>      that x<′y∧x≠y∧¬x<′y. By definition of <′ and
>      injectivity of rep we would have rep(x)<rep(y)
>      ∧rep(x)≠rep(y)∧¬rep(x)<rep(y). A contradiction
>      with < being anti-symmetric.
> 
>      Assume towards a contradiction that <′ is
>      not transitive. Then we would have x,y,z such
>      that x<′y∧y<′z∧¬x<′z. By definition of <′ we
>      would have rep(x)<rep(y)∧rep(y)<rep(z)∧
>      ¬rep(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 Naish’s idea for an infinite tree syntax:
>>>
>>> /* Lee Naish’s idea */
>>> naish(X, Y) :-
>>>     naish([], X, Y).
>>>
>>> naish(S, X, Y) :- compound(X),
>>>     member(Z-Y, S), X == Z, !.
>>> naish(S, X, Y) :- compound(X), !,
>>>     length(S, N),
>>>     X =.. [F|L],
>>>     maplist(naish([X-'$IDX'(N)|S]), L, R),
>>>     Y =.. [F|R].
>>> naish(_, X, X).
>>>
>>> Now define a compare:
>>>
>>> naish_compare(C, X, Y) :-
>>>     naish(X, A),
>>>     naish(Y, B),
>>>     compare(C, A, B).
>>>
>>> Works fine on this example:
>>>
>>> ?- X = s(s(1,Y),0), Y = s(s(1,X),1),
>>>     naish_compare(C, X, Y).
>>> C = (>).
>>>
>>> The residual problem is, that it is extremly slow. Much slower
>>> than the native compare/3 which doesn’t 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
>>
> 
> 
> 

Back to comp.lang.prolog | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

The Million Dollar question of Prolog Mild Shock <janburse@fastmail.fm> - 2025-08-23 14:54 +0200
  AGI will relieve the community (Was: The Million Dollar question of Prolog) Mild Shock <janburse@fastmail.fm> - 2025-08-25 15:11 +0200
    Reflect on Sience not Frog Legs (Was: AGI will relieve the community) Mild Shock <janburse@fastmail.fm> - 2025-08-25 22:55 +0200
      Switching Gears: From Lee Naish to Peter Deutsch (Was: Reflect on Sience not Frog Legs) Mild Shock <janburse@fastmail.fm> - 2025-08-26 11:24 +0200
        Not for pratical use, only for educational use (Re: Switching Gears: From Lee Naish to Peter Deutsch) Mild Shock <janburse@fastmail.fm> - 2025-08-26 11:32 +0200
  Do Prologs Dream of Canonical Sheep? (Was: The Million Dollar question of Prolog) Mild Shock <janburse@fastmail.fm> - 2025-09-05 12:10 +0100
    Electing "conductor" Prolog variables (Was: Do Prologs Dream of Canonical Sheep?) Mild Shock <janburse@fastmail.fm> - 2025-09-05 12:13 +0100

csiph-web