Sunday, February 12, 2023

When is a paper `Easily Available' ?

I was looking at the paper 

                                PSPACE-Completeness of reversible deterministic systems

by Erik Demaine, Robert Hearn,  Dylan Hendrickson, and Jayson Lynch (see here) and came across the following fascinating result which I paraphrase:

The problem of, given balls on a pool table (though it can be one you devise which is not the standard one) and each balls initial position and velocity, and a particular ball and place, it is PSPACE complete to determine if that ball ever gets to that place. 

Demaine et al. stated that this was proven by Edward Fredkin and Tommaso Toffoli in 1982 (see here for a link to the 1982 paper, not behind a paywall). Demaine et al. gave an easier proof with some nice properties. (Just in case the link goes away I downloaded the paper to my files and you can find it here.) 

I needed the bib reference for the FT-1982 paper and rather than copy it from Demaine et al. I wanted to cut-and-paste, so I looked for it in DBLP. I didn't find the 1982 paper but I did find a book from 2002 that reprinted it. The book, Collision-based computing, has a website here. The book itself is behind a paywall.

On the website is the following curious statement:

[This book] Gives a state-of-the-art overview of an emerging topic, on which there is little published literature at the moment. [The book] Includes 2 classic paper, both of which are widely referred to but are NOT EASILY AVAILABLE (E. Fredkin and T. Toffoli: Conservative Logic, and N . Margolous Physics-Like Models of Computation). 

The caps are mine.

Not easily available? I found a link in less than a minute, and I used it above when I pointed to the paper. 

But the book IS behind a paywall. 

Perhaps Springer does not know that the article is easily available. That would be odd since the place I found the article is also a Springer website. 

The notion of EASILY AVAILABLE is very odd. While not quite related, it reminds me of when MIT Press had to pay a few thousand dollars for permission (that might not be the legal term) to reprint Turing's 1936 paper where he defined Turing Machines (he didn't call them that), which is on line here (and other places), for Harry Lewis's book Ideas that created the future. 


  1. Perhaps the papers were not easily available in 2002 when the book was printed.

    As for MIT Press paying for permission, copyright means the copyright holder gets to decide how others can disseminate the item. So, they may allow a copy to be posted on a particular website, but not allow other dissemination.

    I'm not saying that copyright rules are ideal or always make sense. The purpose of copyrights and patents should be to encourage creativity, not make some people oodles of money.

  2. If there is no other option you can always use sci-hub or libgen.

  3. The link *is* behind a paywall for people like me with a residential IP address. Springer wants $35 for it. I think people with institutional associations have very little idea of how unavailable most papers are. And it's even worse now that sci-hub has suspended adding new papers since Dec 2020.

  4. Excellent point. When I log on from home I don't think I am getting to website because of my instutition, but I probably am. But YES, we need to make things more open access in general. arxiv helps some but ot enough.

  5. I think many public university libraries are open to the public and provide the same subscription access to the public that they do to university affiliates. On the other hand, you probably have to actually go to the library rather than access things from the comfort of your residential IP address.