Confusing "decidable problem" and "complete algorithm" (Was: Using Hopcroft & Karp (HK) everywhere)

From	Mild Shock <janburse@fastmail.fm>
Newsgroups	comp.lang.prolog
Subject	Confusing "decidable problem" and "complete algorithm" (Was: Using Hopcroft & Karp (HK) everywhere)
Date	2025-08-14 14:31 +0200
Message-ID	<107kkv4$15tq$1@solani.org> (permalink)
References	<vq4a7g$10843$1@solani.org> <107fqjo$3m3hh$1@solani.org> <107kduo$10b9$1@solani.org>

Show all headers | View raw

Hi,

This is a nice confusion of the highest order.

 > observations on the decidability

Well in summary the existence of a pretest (==)/2
makes Mercio's decidable. Equality on rational trees
is decidable, even if it comes in disguise as Mercio’s
mathematical definition, which gives a total order

which is unfortunately not a natural order:

A=B :⟺ A' =lex B'

A<B :⟺ A' <lex B'

Natural order of rational trees?
https://math.stackexchange.com/a/210730

Why is Mercio’s mathematical definition of equality
decidable? Because it is semantically equivalent to
bisimulation as implemented in (==)/2 , and decidable
is a semantic notion:

Decidability (logic)
In logic, a true/false decision problem is decidableif there
exists an effective method for deriving the correct answer.
Decidability (logic) - Wikipedia

So if you talk about semi-decidable, decidable etc..
its always about the existence of an algorithm in
the large space of effective method according to
the Church hypothesis.

If you want to talk about a particular algorithm
you would use the terminology “incomplete”. Like for
example DFS algorithms are “incomplete” compared to
BFS algorithms on certain problems.

Bye

Mild Shock schrieb:
> Hi,
> 
> Using Hopcroft & Karp (HK) everywhere
> clearly reases the bar. I decided to use
> HK also in compare/3 , just to have it
> 
> detect structure sharing. But here a little
> test comparing with WebPL, only (=)/2 because
> I didn't find compare/3:
> 
> /* WebPL May 2025 */
> test(25).
> True
> (1040.4ms)
> https://webpl.whenderson.dev/
> 
> /* Dogelog Player 1.3.6 */
> :- version.
> :- time(test(25)).
> Dogelog Spieler, Prolog zum Mond, 1.3.6 (02.08.2025)
> (c) 1985-2025, XLOG Technologies AG, Schweiz
> % Zeit 1 ms, GC 0 ms, Lips 125000, Uhr 14.08.2025 12:30
> https://www.dogelog.ch/littab/doclet/live/07_basic/example01/package.html
> 
> SWI-Prolog WASM can also do it fast. The
> old Trealla WASM version cannot do it fast.
> 
> Bye
> 
> P.S.: The test code:
> 
> hydra(0,_) :- !.
> hydra(N,s(X,X)) :- M is N-1, hydra(M,X).
> 
> test(N) :-
>     hydra(N,X), hydra(N,Y), X = Y.
> 
> Mild Shock schrieb:
>>
>> Struggle understanding Hopcroft and Karp (1971) ?
>> No worries Philip Zucker is the man:
>>
>> Co-Egraphs: Streams, Unification, PEGs, Rational Lambdas
>> You can make egraphs support stream like things / rational terms.
>> https://www.philipzucker.com/coegraph/
>>
>> Strange I came up with the same stuff over the last
>> weeks while discussing with @kuniaki.mukai .
>>
>> Lets say 2025 is the year of rational trees!
>>
>> Mild Shock schrieb:
>>> Concerning this boring nonsense:
>>>
>>> https://book.simply-logical.space/src/text/2_part_ii/5.3.html#
>>>
>>> Funny idea that anybody would be interested just now in
>>> the year 2025 in things like teaching breadth first
>>> search versus depth first search, or even be “mystified”
>>> by such stuff. Its extremly trivial stuff:
>>>
>>> Insert your favorite tree traversal pictures here.
>>>
>>> Its even not artificial intelligence neither has anything
>>> to do with mathematical logic, rather belongs to computer
>>> science and discrete mathematics which you have in
>>> 1st year university
>>>
>>> courses, making it moot to call it “simply logical”. It
>>> reminds me of the idea of teaching how wax candles work
>>> to dumb down students, when just light bulbs have been
>>> invented. If this is the outcome
>>>
>>> of the Prolog Education Group 2.0, then good night.
>>>
>>
>

Thread

Prolog Education Group clueless about the AI Boom? Mild Shock <janburse@fastmail.fm> - 2025-03-03 14:18 +0100
  Re: Prolog Education Group clueless about the AI Boom? Mild Shock <janburse@fastmail.fm> - 2025-03-03 14:20 +0100
    Salary Templates if you "Grok" ML / AI [PhDs Negotiate Salaries] (Re: Prolog Education Group clueless about the AI Boom?) Mild Shock <janburse@fastmail.fm> - 2025-03-03 18:03 +0100
  ILP is still dreaming of higher order (Was: Prolog Education Group clueless about the AI Boom?) Mild Shock <janburse@fastmail.fm> - 2025-03-07 23:58 +0100
    Re: ILP is still dreaming of higher order (Was: Prolog Education Group clueless about the AI Boom?) Mild Shock <janburse@fastmail.fm> - 2025-03-08 00:00 +0100
  FYI: Philip Zucker’s Co-Egraphs (Was: Prolog Education Group clueless about the AI Boom?) Mild Shock <janburse@fastmail.fm> - 2025-08-12 18:37 +0200
    Using Hopcroft & Karp (HK) everywhere (Was: FYI: Philip Zucker’s Co-Egraphs) Mild Shock <janburse@fastmail.fm> - 2025-08-14 12:31 +0200
      Confusing "decidable problem" and "complete algorithm" (Was: Using Hopcroft & Karp (HK) everywhere) Mild Shock <janburse@fastmail.fm> - 2025-08-14 14:31 +0200
        DFA algorithms in a Python library (Re: Confusing "decidable problem" and "complete algorithm") Mild Shock <janburse@fastmail.fm> - 2025-08-14 15:14 +0200
      Static Variable Shunting in Dogelog Player (Was: Using Hopcroft & Karp (HK) everywhere) Mild Shock <janburse@fastmail.fm> - 2025-08-16 11:22 +0200
        Dynamic Variable Shunting in WebPL (Was: Static Variable Shunting in Dogelog Player) Mild Shock <janburse@fastmail.fm> - 2025-08-16 11:34 +0200
          SWI-Prolog is still the OG of GC (Was: Dynamic Variable Shunting in WebPL) Mild Shock <janburse@fastmail.fm> - 2025-08-16 11:46 +0200
            Cyclic Term Unification is Accounted (Was: SWI-Prolog is still the OG of GC) Mild Shock <janburse@fastmail.fm> - 2025-08-16 11:59 +0200
            WebPL is an interesting project (Was: SWI-Prolog is still the OG of GC) Mild Shock <janburse@fastmail.fm> - 2025-08-17 18:00 +0200
              Head to Head Race with Scryer Prolog (Was: WebPL is an interesting project) Mild Shock <janburse@fastmail.fm> - 2025-08-17 18:24 +0200
                Does Variable Age make Sense? [Prolog Unification] (Was: Head to Head Race with Scryer Prolog) Mild Shock <janburse@fastmail.fm> - 2026-02-10 12:05 +0100
                Type systems for non-deterministic concurrency [Amir Pnueli] (Was: Does Variable Age make Sense? [Prolog Unification]) Mild Shock <janburse@fastmail.fm> - 2026-07-20 12:20 +0200
                Robin Milners fickle gives non-determinism in practice [Parallel π-WAM] (Was: Type systems for non-deterministic concurrency [Amir Pnueli]) Mild Shock <janburse@fastmail.fm> - 2026-07-20 12:34 +0200
  Sleepy Joe and the Poor South (Local AI Emacs Mode) (Re: Prolog Education Group clueless about the AI Boom?) Mild Shock <janburse@fastmail.fm> - 2025-11-12 12:59 +0100
    Beyond Sleepy Joe around the World (Was: Sleepy Joe and the Poor South (Local AI Emacs Mode)) Mild Shock <janburse@fastmail.fm> - 2025-11-12 13:12 +0100
  GENESIS MISSION: Loosing it over Deep Pokets [Business wants A-Life] (Was: Prolog Education Group clueless about the AI Boom?) Mild Shock <janburse@fastmail.fm> - 2025-11-26 18:07 +0100
  Vanilla Prolog: semi-decidable =\= decidable (Re: Prolog Education Group clueless about the AI Boom?) Mild Shock <janburse@fastmail.fm> - 2026-03-14 20:40 +0100
    Its on the Internet, so it must be true? (Was: Vanilla Prolog: semi-decidable =\= decidable) Mild Shock <janburse@fastmail.fm> - 2026-03-16 11:01 +0100
    Hack + Computed Goto = Leightweigh C_OR (Was: Vanilla Prolog: semi-decidable =\= decidable) Mild Shock <janburse@fastmail.fm> - 2026-07-04 16:58 +0200
      The stack and choice points as an after match (Re: Hack + Computed Goto = Leightweigh C_OR) Mild Shock <janburse@fastmail.fm> - 2026-07-04 17:07 +0200
        Introduction to AI Accelerator Prolog [π-WAM of Dogelog] (Was: The stack and choice points as an after match) Mild Shock <janburse@fastmail.fm> - 2026-07-17 10:49 +0200
          Not praying to the god of lambda calculus [π beats α] (Was: Introduction to AI Accelerator Prolog [π-WAM of Dogelog]) Mild Shock <janburse@fastmail.fm> - 2026-07-17 11:13 +0200
          pi in pi-WAM refers to pi-calculus (Re: Introduction to AI Accelerator Prolog [π-WAM of Dogelog]) Mild Shock <janburse@fastmail.fm> - 2026-07-18 01:22 +0200
            Milners fickle() in pi-WAM [For fun and profit] (Re: pi in pi-WAM refers to pi-calculus (Re: Introduction to AI Accelerator Prolog [π-WAM of Dogelog]) Mild Shock <janburse@fastmail.fm> - 2026-07-18 01:49 +0200
              Robin Milners pi calculus is typeless (Re: Milners fickle() in pi-WAM [For fun and profit]) Mild Shock <janburse@fastmail.fm> - 2026-07-18 11:00 +0200
                Can the Church Turing hypotheses be refuted? [TLo @ FOM] (Re: Robin Milners pi calculus is typeless) Mild Shock <janburse@fastmail.fm> - 2026-07-18 11:10 +0200
          Accelerate Lean! From Theorem 3.11 to Corollary 3.12 [ZMC] (Was: Introduction to AI Accelerator Prolog [π-WAM of Dogelog]) Mild Shock <janburse@fastmail.fm> - 2026-07-19 16:06 +0200
            ANN: Library Pegg, for π-E-graphs [Not EXWM] (Was: Accelerate Lean! From Theorem 3.11 to Corollary 3.12 [ZMC]) Mild Shock <janburse@fastmail.fm> - 2026-07-19 16:21 +0200

csiph-web