From Newsgroup: comp.lang.prolog

Hi,

For Datalog solve/2 will indeed always terminate.
But it will be also utterly disappointing for
left recursive problems:

path(X, Y) :- path(X, Z), edge(Z, Y).
path(X, Y) :- edge(X, Y).

With traces/checking for cycles but without some
fixpoint iteration, it would only compute the
extension path = edge.

What is the cure to this desease, if one wants to
keep the body left to right computation sequencing?
Well OLD resolution is one classic:

OLD Resolution with Tabulation
Sato et al. - July 1986
https://www.researchgate.net/publication/220986525

Bye

Mild Shock schrieb:

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 TuringrCOs 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 EYou (which attempts and fails to compute the
direct diagonal +#rCO) is found to be undecidable in respect to circle-free decider EYoo; 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 rCLmystifiedrCY
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 rCLsimply logicalrCY. 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.

--- Synchronet 3.21d-Linux NewsLink 1.2