triska

As I see it, the result is rather establishing a very fundamental property pertaining to the expressive power of a mechanism, and it can be useful also in practice.

For instance, I have many potential applications of Turing complete formalisms, because I am interested in results of arbitrary computations. The result obtained in the article means that I can use a Neural Network to obtain this, under the conditions outlined in the article, and in the way shown in the article.

This may simplify software architectures, especially in situations where Neural Networks are already applied, and additional mechanisms would otherwise be needed to cover arbitrary computations.

Quoting from the article:

"To prove this we assume that internal activations are represented as rational numbers with arbitrary precision."

And:

"Transformers with fixed precision are not Turing complete."

It will be interesting to see if this leads to better support for arbitrary precision arithmetic in processor architectures.

Personally, I always found that the novel ends on a comparatively hopeful note, especially given the circumstances, the final word being cudów ("of miracles").

Solaris in particular seems more relevant than ever with the rise of ChatGPT and other generative AI services that do not understand what their outputs mean to us, and often produce eery simulacra of life.

The final scenes of Solaris show this situation brilliantly in that their content matches the way it is shown: The scenes themselves mirror the depicted content with perplexing compositions, zooms and transitions, almost as if they were themselves created by an entity that does not understand the content or medium:

https://youtu.be/Z8ZhQPaw4rE?t=9489

Quoting from the book:

"QUESTION: Do you mean, for example, that the hands didn’t move as human hands would move, because the joints were not sufficiently supple?

BERTON: No, not at all. But . . . these movements had no meaning. Each of our movements means something, more or less, serves some purpose . . . "

Quoting from https://earthobservatory.nasa.gov/world-of-change/ENSO:

"El Niño and La Niña reflect the two end points of an oscillation in the Pacific Ocean. The cycle is not fully understood, but the times series illustrates that the cycle swings back and forth every 3-7 years. Often, El Niño is followed immediately by La Niña, as if the warm water is sloshing back and forth across the Pacific. The development of El Niño events is linked to the trade winds. El Niño occurs when the trade winds are weaker than normal, and La Niña occurs when they are stronger than normal. Both cycles typically peak in December.

El Niño and La Niña aren’t the only cycles evident in this image series. The Pacific Ocean is moody: It turns slightly hot or slightly cold every couple of years. This bi-annual pattern isn’t the distinctive, well-defined stripe of warm ocean waters near the equator typical of El Niño, but rather, a general warming of the ocean.

On top of the two-year warm/cold cycle and the El Niño/La Niña pattern is a broader decadal cycle in which the Pacific has a warm and a cool phase. In the 1990s, the Pacific was in a warm phase. The strong El Niño of 1997 marked the end of the warm phase."

So far, I have never before seen an environment group trying to block a mining project referred to as "lobbying". Is the term really that generally used in practice?

Also, the statement is itself wrong already at face value in many situations, for example if someone has a credit card or runs an online shop and is contractually required to hide something. For instance, quoting from https://usa.visa.com/legal/checkout/terms-of-service.html:

"You are responsible for protecting the confidentiality of your username and password(s), if any. In addition, if you choose to be remembered on your device or browser, or link your use of the Visa Solution with a digital wallet, on one or more device(s), you are responsible for protecting the safety of and access to such device(s). It is important that you do so since we are not responsible for any losses you incur as a result of unauthorized use of your Eligible Card and, depending on the circumstances, your Issuer may hold you responsible for unauthorized use of your Eligible Card account."

Another example for mandatory secrecy are confidentiality requirements imposed by professional obligations, such as for lawyers and physicians, in order to ensure fair trials, and for the protection of human dignity.

I think a meta-circular interpreter for Prolog would fit this description nicely. Prolog excels at writing interpreters in general, and in particular admits exceptionally short meta-circular meta-interpreters, i.e., interpreters written in Prolog that can interpret pure Prolog code, including their own source code.

An example of such a meta-circular Prolog interpreter is:

    mi([]).
    mi([G0|Gs0]) :-
            clause(G0, Rs, Gs0),
            mi(Rs).

It can interpret pure Prolog code, a Turing-complete subset of first-order predicate logic. For example, given the following clauses:

    clause(natnum(0), Rs, Rs).
    clause(natnum(s(X)), [natnum(X)|Rs], Rs).

It yields:

    ?- mi([natnum(X)]).
       X = 0
    ;  X = s(0)
    ;  X = s(s(0))
    ;  X = s(s(s(0)))
    ;  X = s(s(s(s(0))))
    ;  ... .

The meta-interpreter's own code can also be represented in this way:

    clause(mi([]), Rs, Rs).
    clause(mi([G0|Gs0]), [clause(G0,Rs,Gs0),mi(Rs)|Ls], Ls).

    clause(clause(Head, Rs0, Rs), Ls, Ls) :- clause(Head, Rs0, Rs).

And now it can interpret its own source code, interpreting any given program, arbitrarily deeply nested. For example:

    ?- mi([mi([mi([natnum(X)])])]).
       X = 0
    ;  X = s(0)
    ;  X = s(s(0))
    ;  X = s(s(s(0)))
    ;  ... .

Tested with Scryer Prolog.

append/3 is a so-called extension of the standard:

    3.70 extension: A facility provided by the processor
    that is not specified in this part of ISO/IEC 13211 but that
    would not cause any ambiguity or contradiction if added
    to this part of ISO/IEC 13211.

This means that every conforming system is free to provide append/3, because it causes no ambiguity or contradiction with the standard. However, by 5.1, every conforming Prolog system must offer a strictly conforming mode:

  e) Offer a strictly conforming mode which shall reject
  the use of an implementation specific feature in Prolog
  text or while executing a goal.

In the case of append/3, this means that there must be a way to run the system without the presence of this predicate. Scryer Prolog satisfies this criterion: In Scryer Prolog, append/3 is only available if library(lists) is loaded, otherwise it is not available. For example, we get:

    $ scryer-prolog -f
    ?- append("Hello, ", X, "Hello, Scryer Prolog!").
       error(existence_error(procedure,append/3),append/3).

append/3 is part of the suggested Prologue for Prolog:

https://www.complang.tuwien.ac.at/ulrich/iso-prolog/prologue

Strings are a good representation for ephemeral data, where allocating an atom would yield additional overhead, via an entry in the atom table that is not needed elsewhere and can only be reclaimed by GC instead of much faster on backtracking.

Another major attraction of strings is that we can use DCGs to reason about them, and we can write this specific example equivalently as:

    ?- phrase(("Hello, ",seq(Cs)), "Hello, Scryer Prolog!").
       Cs = "Scryer Prolog!".

DCGs are another example of a conforming extension, and they are themselves currently being drafted for inclusion in the Prolog ISO standard. In Scryer Prolog, DCGs are available only when library(dcgs) is loaded, so that its default mode after invocation remains strictly conforming.

There was a recent thread Prolog at work with many interesting links and posts:

https://news.ycombinator.com/item?id=34164221

Scryer Prolog was most recently discussed here in October 2021:

https://news.ycombinator.com/item?id=28966133

Since then, a great number of improvements have become available, among them:

The system is now much faster, thanks to a much more compact internal representation of WAM heap cells. In addition, goals that occur as arguments of meta-predicates are now automatically compiled much more efficiently, avoiding superfluous lookups at runtime. Also, Adrían Arroyo Calle has contributed new and much improved HTTP server and client libraries, based on the Rust crate "hyper".

Scryer Prolog 0.9.1 and later versions ship with all these improvements and several smaller corrections and additional features.

Adrían also built the documentation system DocLog that he uses to generate this nice home page of the project:

https://github.com/aarroyoc/doclog

DocLog uses Djota, a Prolog implementation of the markup language Djot:

https://github.com/aarroyoc/djota

Such systems show that nice applications can already be built with Scryer Prolog and its innovations.

Thank you a lot to Mark and everyone who contributed to Scryer Prolog, please keep up the great work!

Very nice!

This solution uses the library predicate list_to_set/2, relating a (known) list Ls0 of elements to a list Ls without duplicates, where the elements occur in the same order in which they first appear in Ls0. I think it is interesting to consider how such a relation can be described in Prolog, and also how efficient it can be.

An immediate solution suggests itself, considering the elements of Ls0 in the order they appear, and keeping track of the elements that have already been "seen". If an element is encountered that has already been seen, ignore it, otherwise it is part of the list Ls we want to describe. We can use a list to keep track of elements that have already been encountered:

    list_to_set(Ls0, Ls) :-
            phrase(firsts(Ls0, []), Ls).

    firsts([], _) --> [].
    firsts([L|Ls], Seen) -->
            (   { member(L, Seen) } ->
                []
            ;   [L]
            ),
            firsts(Ls, [L|Seen]).

This works correctly if the list is ground:

    ?- list_to_set("Corvus corax", Ls).
       Ls = "Corvus cax".

Yet, this solution has a very severe drawback: It is worst-case quadratic in the number of elements, and thus not usable for long lists:

    ?- length(_, E),
       E #> 10,
       N #= 2^E,
       numlist(1, N, Ls0),
       time(list_to_set(Ls0, Ls)).

yielding:

       % CPU time: 0.222s
       E = 11, N = 2048, Ls0 = [1,2,3,4,5,...], Ls = [1,2,3,4,5,...]
    ;  % CPU time: 0.880s
       E = 12, N = 4096, Ls0 = [1,2,3,4,5,...], Ls = [1,2,3,4,5,...]
    ;  % CPU time: 3.518s
       E = 13, N = 8192, Ls0 = [1,2,3,4,5,...], Ls = [1,2,3,4,5,...]
    ;  ... .

So, how to improve it? Well, it may be tempting to use for example a hash or an AVL tree to keep track of the "seen" elements, so that it can be more efficiently decided whether an element has already been encountered. And indeed, that is easy to do, and reduces the runtime considerably.

For example, using the commonly available library(assoc) for AVL trees, providing O(log(N)) lookup:

    list_to_set(Ls0, Ls) :-
            empty_assoc(A0),
            phrase(firsts(Ls0, A0), Ls).

    firsts([], _) --> [].
    firsts([L|Ls], A0) -->
            (   { get_assoc(L, A0, _) } ->
                []
            ;   [L]
            ),
            { put_assoc(L, A0, t, A) },
            firsts(Ls, A).

With this simple change, we get for the query above:

       % CPU time: 0.034s
       E = 11, N = 2048, Ls0 = [1,2,3,4,5,...], Ls = [1,2,3,4,5,...]
    ;  % CPU time: 0.070s
       E = 12, N = 4096, Ls0 = [1,2,3,4,5,...], Ls = [1,2,3,4,5,...]
    ;  % CPU time: 0.155s
       E = 13, N = 8192, Ls0 = [1,2,3,4,5,...], Ls = [1,2,3,4,5,...]
    ;  ... .

The most interesting part is that we can do significantly better, by leveraging Prolog's logic variables to propagate the information whether elements have already been encountered, yielding a very efficient solution where sorting the list Ls0 (or rather: the list of pairs LVs0, where we associate with each element of Ls0 a logic variable that can be used to propagate information by unifying it with other variables and more concrete terms) dominates the asymptotic complexity:

    list_to_set(Ls0, Ls) :-
            maplist(with_var, Ls0, LVs0),
            keysort(LVs0, LVs),
            same_elements(LVs),
            pick_firsts(LVs0, Ls).

    pick_firsts([], []).
    pick_firsts([E-V|EVs], Fs0) :-
            (   V == visited ->
                Fs0 = Fs
            ;   V = visited,
                Fs0 = [E|Fs]
            ),
            pick_firsts(EVs, Fs).

    with_var(E, E-_).

    same_elements([]).
    same_elements([EV|EVs]) :-
            foldl(unify_same, EVs, EV, _).

    unify_same(E-V, Prev-Var, E-V) :-
            (   Prev == E ->
                Var = V
            ;   true
            ).

We now get significantly improved performance:

       % CPU time: 0.003s
       E = 11, N = 2048, Ls0 = [1,2,3,4,5,...], Ls = [1,2,3,4,5,...]
    ;  % CPU time: 0.006s
       E = 12, N = 4096, Ls0 = [1,2,3,4,5,...], Ls = [1,2,3,4,5,...]
    ;  % CPU time: 0.013s
       E = 13, N = 8192, Ls0 = [1,2,3,4,5,...], Ls = [1,2,3,4,5,...]
    ;  ... .

And this is indeed how list_to_set/2 is implemented for example in Scryer Prolog's library(lists):

https://github.com/mthom/scryer-prolog/blob/fd19128530f68c46...

As of version 7, SWI-Prolog is consciously no longer conforming to the Prolog ISO standard in critical aspects, so it is not usable in organizations where standards are of great importance for procurement, warranty and interoperability reasons, and where long-term maintenance and guarantees are required:

https://www.complang.tuwien.ac.at/ulrich/iso-prolog/SWI7_and...

These are valid concerns, arising mostly from inadequate implementations and a lack of modern features in early (and also current) Prolog systems. In the past 20 years, many new language constructs and implementation improvements were introduced and have become widely available in newer Prolog systems to address precisely these problems among others.

For example, inspired by pioneering systems such as XSB Prolog, modern Prolog systems such as Scryer Prolog support alternative execution strategies, internally implemented via delimited continuations as described by Desouter et al., and thus prevent many infinite loops that arise with the default execution strategy:

https://www.ijcai.org/Proceedings/16/Papers/619.pdf

As another example, in 2016, Neumerkel and Kral introduced if_/3 and related predicates, which are now available as library(reif) in Scryer Prolog, and also available for SICStus with advanced compile-time expansions:

https://arxiv.org/abs/1607.01590

As yet further examples, better indexing techniques such as JIT indexing and Scryer Prolog's first instantiated argument indexing help to improve determinism and efficiency automatically, and much improved internal string representations allow efficient parsing of large amounts of data with Prolog's built-in grammar mechanism that is now being drafted for standardisation. Constraints such as dif/2 are now also becoming more widely available after decades of being largely ignored by implementors.

As long as we keep to the pure monotonic core of Prolog, conjunction and disjunction are indeed semantically commutative, and different execution strategies are applicable. Of course, using !/0 and other constructs that rely on specific execution strategies forfeits this advantage.

In your second example, I get an exception (it does not "explode"), and this is also not a "bug". In your second example, the default search strategy is unable to derive whether above(a,c) is a logical consequence of the program. The existence of such cases is expected when using the default execution strategy (SLD resolution), which sacrifices completeness for efficiency.

A key advantage of using a declarative programming language such as Prolog is that we can change the execution strategy. For example, I tried your code in Scryer Prolog and added 2 directives as the first two lines to enable an execution strategy called SLG resolution instead of the default strategy:

    :- use_module(library(tabling)).
    :- table above/2.

    on(a,b). on(b,c). above(X,Y) :- above(X,Z), on(Z,Y). above(X,Y) :- on(X,Y).

Now I get:

    ?- above(a,c).
       true
    ;  ... .

So, with a different search strategy, the Prolog system is also able to derive that above(a,c) holds, like Clingo.

Note that answer set programming cannot help in any way when I need a program to perform side effects such as initiating a network connection, hosting a web page, parsing a file etc., whereas Prolog is extremely useful and appropriate for such applications. So, the fact that the default execution strategy of Prolog is not adequate to solve this specific example is not a sensible argument for or against Prolog.

A recent article from the Austrian Federal Computing Centre, using Prolog to analyze eligibility criteria for grants:

https://www.brz.gv.at/en/BRZ-Tech-Blog/Tech-Blog-7-Symbolic-...

In this way, several interesting questions can be answered, such as: Are there grants that have the same prerequisites? How many companies are not eligible for any grant? Are there grants where eligibility also implies other grants? etc.

Prolog is becoming more interesting now that several conforming and free implementations with comprehensive features arise, notably Scryer, Tau and Trealla Prolog as the most recent systems, and interesting bindings for other languages such as ichiban/prolog for Go. On the Datalog side, Google have recently published a Datalog system called Mangle, which supports the Datalog subset of Prolog as a proper subset.

Quoting from the article:

"Take, for instance, a loop ..."

Personally, I write most programs in a logic programming language that has no loops. I wonder whether the engaged brain areas also depend on the programming language. The previous study used for example Python, an imperative language, and mentiond "Language system responses during code comprehension are weak and inconsistent":

https://elifesciences.org/articles/58906

Could it be that language system responses are stronger for more declarative programming languages, where a clear description of the problem is of greater importance?

A classic reference: The British Nationality Act as a Logic Program:

https://www.doc.ic.ac.uk/~rak/papers/British%20Nationality%2...

Parts of the constitution of Japan in Prolog:

https://github.com/bitlaw-jp/the-constitution-of-japan

A recent project involving the formalization and automated analysis of criteria for grants:

https://www.brz.gv.at/en/BRZ-Tech-Blog/Tech-Blog-7-Symbolic-...

Regarding the negative impact of Postel's suggestion, see also The Harmful Consequences of Postel's Maxim:

https://datatracker.ietf.org/doc/html/draft-thomson-postel-w...

In Section 4, they define an alternative design principle based on the lessons of protocol deployment:

Protocol designs and implementations should be maximally strict.

Very interesting!

Regarding the sentence: "The first instruction clears the direction flag.", I noticed that cld is the second instruction in the listing, I suppose that is a small mistake in the article?

PostScript is such a beautiful language! I used to study the PostScript reference manual for hours at a time, in awe of its elegance and perfection:

https://www.adobe.com/jp/print/postscript/pdfs/PLRM.pdf

How interesting a web would be with embeddable PostScript figures! Yes it's Turing-complete and all, and yes that's no problem: Interpret these figures with a timeout, make the interpretation interruptible, use a sandbox or different threads for rendering etc. HTML+CSS+user interaction is Turing complete as well, and we can still browse the web despite this.

Thank you a lot for PostScript!

> What we want is a well-behaved, predicable mix of programming and those relational operations. We have to end this SQL madness.

These are great goals! Thank you a lot for working on them, and for taking the time to participate here!

> We should be able to isolate syntactic fragments where it is easy to ensure safety properties, at the minimum the datalog fragment.

Again a great goal! Luckily, for every given Prolog program, it can be decided statically whether it is in the usually considered Datalog fragment. Likewise, for every given Prolog program, many things can be statically decided, for example it can be said statically, i.e., by just "looking" at the program without running it, with certainty that impure constructs do not occur in a given Prolog program and that these transformations can be applied without changing the declarative meaning of the program.

I think it is a very good idea to restrict oneself to a fragment of Prolog, especially if you need a lot of leeway to optimize programs, and to reason about them. For example, query optimization is much easier if you know that no side-effects occur in a Prolog program.

The question is whether all this needs any syntax beyond what standard Prolog already provides. Prolog is a very flexible language and supports user-defined operators. If possible, I recommend to keep to this standardized syntax, and to use a sensible fragment of it to facilitate reasoning, at least for as many programs as possible. The availability of existing teaching material and research papers you mentioned is another excellent argument in favor of this approach. It is perfectly OK to only support a proper subset of full Prolog, in fact that is exactly what Datalog does!

> Consider Soufflé, designed for large scale program analysis. Or LogiQL, designed for efficient incremental evaluation.

I have now looked up these systems: They are far removed from standard Prolog syntax, much farther than the system outlined in the posted article, which uses almost Prolog syntax to such an extreme extent that one of the given examples is already valid Prolog syntax and even a valid Prolog program without any changes. Therefore, the question I posted above ("If you are that close to using Prolog syntax, ...") does not apply to the same extent to these systems.

> You also failed to disclose that you are not exactly unbiased individual here.

Personally, I believe I have a solid grasp on the benefits of using standard Prolog syntax and the disadvantages of so slightly deviating from it, and I also believe that the question I asked is justified and what I stated in this thread is true.

If you see a need for any disclosure beyond what I stated above, please add it and what you believe to be the nature of my bias as your reply to this post for everyone to see. Thank you a lot!

The code snippets shown on the page are almost valid Prolog syntax. The only issues that prevent them from being actual Prolog syntax are, as far as I can tell, very minor syntactic issues. For example, != cannot be defined as an infix operator in Prolog because ! is a so-called solo char and therefore != is not admissible as a single token in Prolog. The obvious fix for this concrete issue is to replace every occurrence of != in these snippets with the well-known Prolog predicate dif/2 which holds if and only if its two arguments are different.

For instance, the first example from the page:

    projects_with_vulnerable_log4j(P) :-
      projects(P),
      contains_jar(P, "log4j", Version),
      Version != "2.17.1",
      Version != "2.12.4",
      Version != "2.3.2".

would become:

    projects_with_vulnerable_log4j(P) :-
      projects(P),
      contains_jar(P, "log4j", Version),
      dif(Version, "2.17.1"),
      dif(Version, "2.12.4"),
      dif(Version, "2.3.2").

or, shorter and equivalently, by using full Prolog including higher-order predicates such as maplist/2:

    projects_with_vulnerable_log4j(P) :-
      projects(P),
      contains_jar(P, "log4j", Version),
      maplist(dif(Version), ["2.17.1","2.12.4","2.3.2"]).

This third version could of course be generated automatically from the snippet above. We could also define dif or many other tokens as infix operators, so that we can use operator notation as in the original snippet, all while keeping to standard Prolog syntax.

Analogously for |> and the let-bindings that occur in the sample snippets: Chances are that they can be expressed somehow also with standard Prolog syntax with suitable operator definitions, or with small conforming extensions if absolutely required.

The third example in the README is already perfectly valid Prolog code, and can be parsed and interpreted with every conforming Prolog system:

    contains_jar(P, Name, Version) :-
      contains_jar_directly(P, Name, Version).

    contains_jar(P, Name, Version) :-
      project_depends(P, Q),
      contains_jar(Q, Name, Version).

The main issue here is: This "own Datalog" is extremely close to Prolog syntax, much closer to Prolog than any other Datalog "variant" I have so far seen on HN. The question therefore is: Why not go the small extra step and just use standard Prolog syntax? One advantage of this is that such programs could then be read and reasoned about directly (i.e., without requiring any manual parsing) with every conforming Prolog system. Another advantage is that such programs would also automatically benefit from all improvements in Prolog engines, either via meta-interpretation or by virtue of being valid Prolog programs too. For instance, the first snippet shown in the README, with the small syntactic change I outlined, is already a valid Prolog program and can be run with SICStus Prolog etc.

Using Prolog syntax does not mean that that the programs have to be interpreted in the same way as Prolog would by default. It is also possible to syntactically include constructs that cannot be directly interpreted in Prolog, but require a custom interpreter. The point about syntactic compatibility stands regardless.

Yes, the subset of Prolog that is called Datalog can be interpreted in such a way that termination is guaranteed, and that is a nice and valuable property of this specific subset, i.e., the functor-free subset, of Prolog.

This is a good example to illustrate why it can be useful to interpret specific Prolog programs and fragments in specific ways, which may also differ from the default execution strategy.

As a specific instance of such an execution strategy, we can again consider SLG resolution: If we interpret any pure Prolog program that does not use compound terms with SLG resolution, then every query we post terminates universally.

Yes well, as you mention, that is only the default execution strategy, and nothing prevents us from using other execution strategies for either language. In fact, the main advantage of using a declarative language such as Prolog or Datalog is precisely that it can be readily interpreted with different execution strategies, and indeed many Prolog implementations already provide alternative execution strategies, the most common of which is currently SLG resolution, also known as tabling. Alternative execution strategies are applicable as long as you keep to the pure monotonic core of the language.

The fact that the default execution strategies of Prolog and Datalog differ is not a valid argument for or against using a slightly different syntactic formalism. If, as seems plausible, an alternative execution strategy of Prolog can provide the same semantics as Mangle and other Datalog "variants", then it may be worth considering doing that instead of devising a different syntactic formalism, especially if the alternative syntactic formalism is already so close to valid Prolog syntax as it is in this concrete case.

This seems already almost valid Prolog syntax, which is also a syntactic superset of Datalog.

The main question I have for implementors of Datalog and Prolog variants like this: If you are that close to using Prolog syntax, why not go all the way and rely fully on Prolog, a language for which a well-defined ISO standard and several interesting implementations already exist. One of the key benefits you get in this way is Prolog's strength for meta-programming and reasoning about programs with the same formalism you use to state the specifications and queries. Abstract interpretation, query optimization etc. can be easily implemented in this way, instead of having to parse an additional formalism.

It may be possible to implement such Prolog-"variants" entirely within Prolog by defining suitable infix or prefix operators, or adding conforming extensions in implementations. A conforming extension is one that does not conflict with existing ISO syntax. For example, something that would be a syntax error in conforming Prolog implementations could be used as an implementation-specific extension.

The "new-fangled" AI, as the article calls it, is often useful when the stakes are low, and you can accept mistakes in outcomes. Examples of such applications are: trying to determine which of your friends occur in a photo, which movies a subscriber may be interested in, or which action could lead to victory in a computer game. Getting a rough translation of a newspaper entry, as mentioned in the article, is also a good example.

As soon as you need reliable outcomes, such as certainty whether an erroneous state can arise in a program, whether a proof for a mathematical conjecture exists, or whether a counterexample exists, exhaustive search is often necessary.

The question then soon becomes: How can we best delegate this search to a computer, in such a way that we can focus on a clear description of the relations that hold between the concepts we are reasoning about? Which symbolic languages let us best describe the situation so that we can reliably reason about it? How can we be certain that the computed result is itself correct?

The article states: "The heart of GOFAI is searching – of trees and, more generally, graphs." I think one could with the same conviction state: "The heart of GOFAI is reasoning – about relations and, more generally, programs."

It appears this may be incorrectly marked as a dupe: An issue of Byte Magazine about declarative languages (Volume 10 Number 08) was recently discussed here:

https://news.ycombinator.com/item?id=32828569

However, the present submission is Volume 12 Number 09, with different authors and contents.

I also highly recommend this book!

Regarding the sentence "One that he doesn’t discuss much but that is particularly pertinent to today, is the accretion of laws and regulations." which appears in the review: I think all these laws and regulations can be regarded as being part of the increasing bureaucracy that Tainter identifies as the cause of eventual collapse of complex societies.

One thing I would add, in addition to the diminishing marginal return of bureaucracy that Tainter mentions, is the tendency of contemporary administrations to create more bureaucracy even when their own stated goal is to reduce bureaucracy or increase efficiency, for example by trying to collect and compare precise numbers that show how they have become more efficient at a task that is in essence not really quantifiable. A related book I recommend particularly in that regard is Le Règne de la Quantité et les Signes des Temps by René Guénon.