Computers and Automata (1953) | Hacker News Reader

Computers and Automata (1953)

fermatslibrary.com

82 pointsBerislavLopac14 comments

"It is known that salesmen always tell the truth and engi- neers always tell lies. G and E are salesmen. C states that D is an engineer. A declares that B affirms that C asserts that D says that E insists that F denies that G is a sales- man. If A is an engineer, how many engineers are there?"

Now that is a curious puzzle in the sense that I can't think how to express it in Prolog. You'd need to assert the truth of assertions which implies quantifying over assertions, and Prolog doesn't allow that. I'm sure I'm making this much more complex than it need be, there has to be a much more straightforward way, any ideas please?

The article suggests using Boolean logic, so let's apply it: One way to solve this is to introduce a Boolean variable for each of A,...,G, and to use 1 to denote that a statement is true, and also to denote that the corresponding person tells the truth. It then remains to relate the truth of each statement to the truthfulness of the person making the statement.

In Prolog, we can express these relations with CLP(B), constraint logic programming over Boolean variables:

    ?- use_module(library(clpb)).
       true.
    ?- sat(G),
       sat(E),
       sat(C =:= ~D),
       sat(A =:= (B =:= (C =:= (D =:= (E =:= (F =:= ~G)))))),
       sat(~A),
       labeling([A,B,C,D,E,F,G]).

Yielding 4 solutions that satisfy all constraints:

       G = 1, E = 1, C = 0, D = 1, A = 0, B = 0, F = 1
    ;  G = 1, E = 1, C = 0, D = 1, A = 0, B = 1, F = 0
    ;  G = 1, E = 1, C = 1, D = 0, A = 0, B = 0, F = 1
    ;  G = 1, E = 1, C = 1, D = 0, A = 0, B = 1, F = 0.

From this, it is clear that there are 3 engineers, in all possible situations consistent with the description.

If we omit the labeling/1 goal which enumerates all solutions, then we get a symbolic representation of all remaining constraints:

    G = 1, E = 1, A = 0, clpb:sat(C=:=D#B#F), clpb:sat(C=\=D).

From this, it is clear that there are at least 2 engineers in every solution: A (as stated in the description of the puzzle), and either C or D (but not both).

Tested with Scryer Prolog.

You're a treasure sir!

The thing I find especially interesting about these sorts of puzzles is the translation from the word problem to the logical formalism. It seems like a separate domain from solving the problem itself.

With Prolog, we can often very naturally map such puzzles to programs, or at least to declarative descriptions that can be easily interpreted by Prolog programs.

For instance, in this concrete case, with a suitable operator definition for the operator says, we can write:

    :- op(800, xfy, says).

    solution([A,B,C,D,E,F,G]) :-
            G = salesman,
            E = salesman,
            C says D = engineer,
            A = engineer,
            A says B says C says D says E says F says G = engineer.

It is then left to interpret the statements, which we can do for example with:

    :- use_module(library(dif)).

    engineer says Stmt :- false(Stmt).
    salesman says Stmt :- true(Stmt).

    false(A = B) :- dif(A, B).
    false(engineer says Stmt) :- true(Stmt).
    false(salesman says Stmt) :- false(Stmt).

    true(A = A).
    true(engineer says Stmt) :- false(Stmt).
    true(salesman says Stmt) :- true(Stmt).

Yielding:

    ?- solution(S).
       S = [engineer,engineer,engineer,salesman,salesman,salesman,salesman]
    ;  S = [engineer,salesman,engineer,salesman,salesman,engineer,salesman]
    ;  S = [engineer,engineer,salesman,engineer,salesman,salesman,salesman]
    ;  S = [engineer,salesman,salesman,engineer,salesman,engineer,salesman]
    ;  false.

That is most excellent, thank you

Take a look at the abomination of HTML on that page. All 7 megabytes of it.

PDF version:

https://webmuseum.mit.edu/files/2007.030.010-ref1.pdf

I'm curious how you came across this copy. It doesn't seem to be reachable from webmuseum.mit.edu's front door.

This is the first result on DuckDuckGo when searching for the exact title of this post: https://duckduckgo.com/?q=Computers+and+Automata+(1953).

Thanks. This seems to be an instance where DDG/Bing's feelers are better than Google's. It only leads to another question, though, which is how they came across it. The Wayback Machine didn't know anything about it before.

Since they don't have Apache configured to hide directory listings, there's a whole trove of scans and other material listed at <https://webmuseum.mit.edu/files/>.

Does anyone know how to find the paper cited in the section on Logic Machines?

McCallum D. B. and Smith J. B.. Mechanized reasoning—logical computers and their design.

I can only find a review of it. This is an area of interest for me as I want to design educational logic machines to teach proofs.

https://aslonline.org/journals/the-journal-of-symbolic-logic...

Contact them and ask

Unfortunately I can only access volumes of 'Electronic Engineering' starting with Vol. 30, and the one you want is 23.

This is the back matter, which seems to be a Table of Contents:

https://annas-archive.org/md5/c50b9ec404b79e6a7d6ad77e9ef55f...

Front matter:

https://annas-archive.org/md5/e9080f059fa914cc7ae31e2790b267...

Reply on news.ycombinator.com