Vanilla Prolog: semi-decidable =\= decidable (Re: Prolog Education Group clueless about the AI Boom?)

From	Mild Shock <janburse@fastmail.fm>
Newsgroups	comp.lang.prolog
Subject	Vanilla Prolog: semi-decidable =\= decidable (Re: Prolog Education Group clueless about the AI Boom?)
Date	2026-03-14 20:40 +0100
Message-ID	<10p4dif$1nve7$1@solani.org> (permalink)
References	<vq4a7g$10843$1@solani.org>

Show all headers | View raw

Hi,

Somebody just changed the Vanilla Prolog
meta interpreter from:

solve(true) :- !.
solve((A,B)) :- !, solve(A), solve(B).
solve(H) :- clause(H, B), solve(B).

Into a cycle checking interpreter. It makes
certain Datalog programs and queries complete,
but it doesn't make Horn clauses complete:

solve(A) :- solve(A, []).

solve(true, _) :- !.
solve((A,B), L) :- !, solve(A, L), solve(B, L).
solve(A, L) :- member(B, L), A =@= B, !, fail.
solve(H, L) :- clause(H, B), solve(B, [H|L]).

Bye

P.S.: Here is a proof for Datalog:

Since Datalog has only constants and variables,
no function symbols at all, there are only finitely
many literals at runtime modulo (=@=)/2.

Q.E.D.

dart200 schrieb:
 > The following claim from p246 of Turing’s seminal paper On Computable 
Numbers is a fallacy:
 >
 > /the problem of enumerating computable sequences is equivalent to the 
problem of finding out whether a given number is the D.N of a circle- 
free machine, and we have no general process for doing this in a finite 
number of steps/
 >
 > For any given computable sequence, there are _infinite_ circle-free 
machines which compute that particular sequence. Not only can various 
machines differ significantly in the specific steps to produce the same 
output, machines can be changed in superficial ways that do not 
meaningfully affect the steps of computation, akin to modern no-op 
statements or unreachable code
 >
 > The problem of enumerating computable sequences, however, only 
depends on successfully identifying _one_ circle-free machine that 
computes any given computable sequences. While identifying more than one 
can certainly be done, it is _not_ a requirement for enumerating 
computable sequences, as _one_ machine computing a sequence /suffices to 
output any and all digits of that sequence/
 >
 > The problem of enumerating computable sequences is therefore _not_ 
actually equivalent to a _general process_ of enumerating circle-free 
machines, as there is no need to identify all circle-free machines which 
compute any given computable sequence
 >
 > Said problem is only equivalent to a _limited process_ of enumerating 
circle-free machines. The machine which identifies circle-free machines 
only needs the limited power of determining _at least one_ circle-free 
machine for any given computable sequence, _not all_ machines for any 
given computable sequence
 >
 > Because of this fallacy, the proof found on the following p247, where 
an ill-defined machine 𝓗 (which attempts and fails to compute the 
direct diagonal β’) is found to be undecidable in respect to circle-free 
decider 𝓓; does not then prove an impossibility for enumerating 
computable sequences. As the problem of enumerating /all circle-free 
machines/ is _not_ equivalent to that of enumerating /just computable 
sequences/
 >
 >

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