Saturday, 27 August 2016

Nan.Numerics.Prime (in Prolog)

Nan.Numerics.Prime/Prolog 1.2.2-beta

A simple prime number library
Copyright 2016 Julio P. Di Egidio
Licensed under GNU GPLv3.


Module prime provides predicates to test (positive integer) numbers for
primality, find divisors and factor numbers, generate prime numbers in some
interval, find consecutive prime numbers, and save/load all prime numbers
up to some value to/from a file or stream.

Implements a variant of the Miller-Rabin primality test that is
deterministic for numbers up to 3317044064679887385961980, otherwise
it is probabilistic with the number of iterations fixed at 20.

NOTE: Since the primality test in use is probabilistic in general, this
library is not suitable for cryptographic applications.

See the README file for more details.

This library was developed and tested with:
SWI-Prolog 7.3.25 -

(I am planning for a JavaScript version.)

Wednesday, 16 September 2015

Answer Sources: from Fluents to Interactors

This is a follow-up to my previous post "Answer Sources in Prolog (SWI) - Preview" [1]. Here I present the flow diagram for the worker loop with support for the return operation. Implementation of the return operation upgrades our answer sources from fluents [2] to interactors [3].
[1] My post, "Answer Sources in Prolog (SWI) - Preview":

[2] Paul Tarau, "Fluents: A Refactoring of Prolog for Uniform Reflection and Interoperation with External Objects":

[3] Paul Tarau and Arun Majumdar, "Interoperating Logic Engines":

Thursday, 3 September 2015

Answer Sources in Prolog (SWI) - Preview

I have implemented an initial version of Answer Sources in SWI-Prolog [1], now submitted for preliminary discussion to comp.lang.prolog [2]. For the rationale and design, I have followed Paul Tarau on "fluent sources" [3], although with some important differences.

[1] Code preview with answer sources and the basic combinators:

[2] (Short) presentation and discussion on comp.lang.prolog:

[3] Paul Tarau, "Fluents: A Refactoring of Prolog for Uniform Reflection and Interoperation with External Objects":

Wednesday, 15 July 2015

Symmetric Twins Paradox

[NOTE: I am thinking about withdrawing this article as essentially incorrect!]

In the context of special relativity, we present a twins experiment that is symmetric between the twins, so that a paradox appears inescapable, in the form of a violation of the principle of causality.

Here is the experiment (we would argue that effects of acceleration can be made arbitrarily small in our setup):

  == The twins, call them L and R, are each given a clock at birth and get the clock fixed to their body: the two clocks have been previously synchronised.  Assume, for simplicity, that the common origin of space-time for the clocks is set to the moment and place of the twins' birth, as well as a common choice of coordinates is made, such that the twins, at that very moment, share the same frame of reference (up to arbitrary precision).
     Just after birth, the twins (with their clocks) are each embarked on a rocket.  Assume collinear motion for simplicity.  The two rockets start in opposite direction relative to the origin, carrying L and R respectively.  The plan is for the rockets to fly away from each other at some fixed (appropriately high) constant speed for some fixed (appropriately long) proper time, then simply invert course and fly back at opposite speed to the point of origin (in space), and stop there.  (Effects of acceleration can be minimised by making the total proper time the rockets are subject to acceleration appropriately small relative to the total proper time of the journey.)
     The twins at that point rejoin, again sharing a common frame of reference (up to arbitrary precision).  We ask what the two clocks measure for each twin in this common frame. ==

To compute results, we apply special relativity.  (We advise readers go through this little but essential exercise by themselves.)  We find that R's clock looks late (i.e. back in time) to L, but, *at the same time* (twins and clocks are in a common frame of reference), L's clock looks late to R!  This conclusion is an inescapable consequence of the theory, and now the problem becomes how to make sense of these results.  In fact, since all clocks are affected, including the biological ones, at the end of the journey each twin effectively finds the other younger than himself: then, per *reciprocity* (causality), i.e. that in the same frame of reference, if I am older than you, you must be younger than me, we can argue that each twin is at the same time younger and older than the other, which is indeed absurd!

Note that the absurdity would not be so patent if we just let the two clocks travel, hence we sent the twins, too: not because the presence of the twins is necessary for relativistic effects to occur, the clocks must be late relative to each other regardless of anyone observing them, rather because only the twins can "testify" that the conclusion of the experiment, so special relativity theory, is indeed at odds with the principle of *causality*.

Bottom line: if special relativity is correct, it must be incomplete.

Saturday, 18 April 2015

Cheryl's birthday in Prolog

Cheryl's Birthday - The Math Question That Went Viral
"One word problem from a Singaporean school exam briefly became the talk of the Internet last weekend."

I have put together two solutions in Prolog (in SWI-Prolog, last updated 2015-04-20T19:40:00+01:00), the source code can be downloaded here:

The first solution ( uses lists and aggregates:
?- problem(cbdate, BDate).
% 563 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
BDate = [7, 16].

?- time((between(1,1000,_),p_cbdate_input(CBDates),p_cbdate(CBDates, BDate),fail;true)).
% 563,001 inferences, 0.218 CPU in 0.220 seconds (99% CPU, 2577827 Lips)
The second solution ( uses lists:
?- problem(cbdate, BDate).
% 5,163 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
BDate = [7, 16].

?- time((between(1,1000,_),p_cbdate_input(CBDates),p_cbdate(CBDates, BDate),fail;true)).
% 5,164,001 inferences, 1.513 CPU in 1.520 seconds (100% CPU, 3412614 Lips)
The first solution, i.e. the implementation leveraging aggregates, turns out to be significantly faster...

Wednesday, 26 February 2014

Hilbert's impossible hotel

"Consider a hypothetical hotel with a countably infinite number of rooms, all of which are occupied. [...] Suppose a new guest arrives and wishes to be accommodated in the hotel. Because the hotel has infinitely many rooms, we can move the guest occupying room 1 to room 2, the guest occupying room 2 to room 3 and so on, and fit the newcomer into room 1." (*)

But we can prove that, if the hotel is full, accommodating new guests is in fact impossible:

Indeed, to say that the hotel is fully occupied is to say that, for all n in N, room n is occupied. Thus, a fortiori, room 1 is occupied and, for all n in N, if room n is occupied, room n+1 is also occupied. Which in turn is equivalent to saying that there is no n in N such that room n+1 is available. Hence, no more guests can be accommodated. QED.

Note that what I am actually showing is that, granted the usual inductive definition for the natural numbers (a sequence), the hotel simply can never be full; conversely, that there can be no such thing as a hotel (a set) that is potentially infinite. In other words, the simply endless is just not of the same (logical) quality of the actually infinite, that is what Hilbert's hotel is showing. Consequently, nothing peculiar about infinite sets can be proven via plain finite induction on sequences.


Thursday, 26 August 2010

Se programmo...

Professional, un-professional, de-professional, re-professional.

Otherwise, the ins and outs of the pros and cons.

Publicly private.

Bah, intanto lei dorme.

Friday, 10 July 2009

A semantic space-dimension for the Web

How to give a *sensible* space-dimension to the Web.

This is an open project.

Discussion at:
"A space-dimension to the Web: a combinatorial optimisation problem"

=== Setting:

Let G be a weighted, directed graph.
Let S be a lattice space for G.
Let M be a physical model for G.
Let U be (the absolute value of) the potential energy (in M over S, given G)

=== Problems:

Problem 1 (optional): Express U.
Problem 2 (optional): Minimize U.
Problem 3: Express and minimize U, given the following constraints:

- Constraint 3.CG1: Weights in G have positive rational values.

- Constraint 3.CG2: G is sparse.

- Constraint 3.CG3: G is dynamic, i.e. nodes and edges change (appear, desappear, change their weight). The dynamic is by discrete singular events, changes are smooth.

- Constraint 3.CS1: S is a diophantine circle where positions start from zero along the circumference, and the distance function x is:

    let c be the circumference (i.e. number of nodes in G)
    let x' = x1 - x2 (absolute distance, integer >= 0)
    x := x'      , if x' <= c/2
         c - x'  , otherwise
    (i.e. distance along the shortest arc, integer >= 0)

- Constraint 3.CM1: Within model M, the force F is:
    let i,j be non-negative integers indexing nodes in G
    f_ij = k_ij * x_ij , if exists in G edge i->j with weight k_ij
           0             , otherwise
    (i.e. absolute elastic force, rational >= 0)
    F = sum_i sum_j f_ij
    (total force, rational >= 0)

- Constraint 3.CU1: Given that G is dynamic (see CG3), we want to minimise U and keep it minimised!

=== Solutions:

Our solution to Problem 3 at the moment consists in a "local approach".  We build a graph that is near-to-optimal (by inserting any new node at a location such to minimise the total energy change), plus we have a process that keeps iterating the configuration space for local improvements (by swapping adjacent nodes).  The idea is that this process should be able to keep up with changes (which are smooth, see 3.CG3 and 3.CU1), and this together with the strategy of insertion should be enough to keep the system (at least!) at a near-to-optimal minimum.  Simulated annealing can also be easily implemented.

Incidentally, in the setting of Problem 3 there is no role for node weights.  This is a choice, not a simplification, related to semantic considerations.  This can be discussed: we are after a *sensible* way to give a space-dimension to the Web.

Tuesday, 11 March 2008

Radical contradiction

Technically speaking,

We have blown up the "root of contradiction" with an _atomic_ bomb.

To the casual philosophers we are, I will show the links below.

To the professional programmer: a crack is not a hack, but a hack is a crack.

Keep up the go(o)d work.


Julio Di Egidio
Re: Question about proof by contradiction
Posted: Mar 10, 2008 11:12 AM


BTW, here is an extract from a letter from Wittgenstein to Russel, 1921, which I think sheds some light (I'm

afraid I'll have to traslate, I've got it in Italian):

"I believe our problems track down to _atomic_ propositions. You'll see it if you try to precisely explain

how the Copula is such propositions has meaning. I cannot explain it and I believe that, once an exact answer

is given to this question, the problem of <> and of the apparent variable will be _much_ nearer its

solution, if not solved. Now I think above <> (the good old Socrates!)."

The good old Ludwig!!

Explaining that meaning, by means of the empty set "we" are, is indeed what I have shown (again, until dis-




Re: Question about proof by contradiction
Posted: Mar 10, 2008 5:46 PM

> >> Proof by contradiction can be formalized as
> >> (P -> (A and not(A))) -> not(P).
> The proof in question, in fact, does not even use proof by
> contradiction. It has the form
> (P -> not(P)) -> not(P).
> This is not a proof by contradiction.


Does anything interesting happen if we transform them somewhat?

(P -> (A and not(A))) -> not(P)
(P -> false) -> not(P).
(not(P) or false) -> not(P)
not(P) -> not(P)

Well, I seem to have destroyed the formula's essential nature
by these manipulations. How did THAT happen? Apparently
truth-value-preserving transformations don't preserve some things
that aren't truth values.