Alan Turing’s bibliography with links

The importance of the work of Alan Turing is well known to everybody. The most complete resources on Turing’s work are The Turing Digital Archive, the book “The essential Turing” of Jack Copeland and the volumes of his “Collected works”. The problem with the Digital Archive is that it contains scans of manuscripts from which is not so easy to read, yet I think it is very interesting to browse.

Below, I list most of Turing’s papers and some links for them. The links are freely accessible and they lead to easily read pdf files that are scans or reprints of the original publications or at least they are very close to it.

The links are listed as found on the web; any possible copyright issues or broken link issue should regard the owner of the site that hosts the linked files. In case you have any suggestions for the list please add a comment.
At the end you may find something that should be an anecdote  but it is a real problem in academic publications.

Turing, Alan M. On computable numbers, with an application to the Entscheidungs problem. Proceedings of the London Mathematical Society, 2 s. vol. 42 (1936–1937), pp. 230–265.

link

Turing, Alan M. "On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction." Proceedings of the London Mathematical Society 2.1 (1938): 544-546.

link

Turing, Alan M. "Equivalence of left and right almost periodicity." Journal of the London Mathematical Society 1.4 (1935): 284-285.

Turing, Alan M. "Computability and λ-definability." The Journal of Symbolic Logic 2.04 (1937): 153-163.

link

Turing, Alan M. "The þ-function in λ-K-conversion." The Journal of Symbolic Logic 2.04 (1937): 164-164.

link 

Turing, Alan M. "Systems of logic based on ordinals." Proceedings of the London Mathematical Society 2.1 (1939): 161-228.

link

Turing, Alan M. "The use of dots as brackets in Church's system." The Journal of Symbolic Logic 7.04 (1942): 146-156.

Newman, M. H. A., and Turing, A. M. "A formal theorem in Church's theory of types." The Journal of Symbolic Logic 7.01 (1942): 28-33.

Turing, Alan M. "Turing’s treatise on Enigma." Unpublished Manuscript (1939).

link 

Turing, Alan M. "Lecture to the london mathematical society on 20 february 1947." MD COMPUTING 12 (1995): 390-390

link 

Turing, Alan M. "Some calculations of the Riemann zeta-function." Proceedings of the London Mathematical Society 3.1 (1953): 99-117.

Turing, Alan M., and Bayley, D. "Report on Speech Secrecy System DELILAH, a Technical Description Compiled by AM Turing and Lieutenant D. Bayley REME, 1945–1946." Cryptologia 36.4 (2012): 295-340.

link

Turing, Alan M. "Proposed electronic calculator, report for national physical laboratory, teddington." AM Turing’s ACE Report of 2 (1946).

Turing, Alan M. "Lecture on the Automatic Computing Engine (1947)." The Essential Turing by  B. Jack Copeland (2004): 362.

Turing, Alan M. "Rounding-off errors in matrix processes." The Quarterly Journal of Mechanics and Applied Mathematics 1.1 (1948): 287-308.

link

Turing, Alan M. "Intelligent Machinery, A Heretical Theory." The Turing Test: Verbal Behavior as the Hallmark of Intelligence (1948): 105.

link

Turing, Alan M. "Intelligent machinery-national physical laboratory report. b. meltzer b., d. michie, d.(eds) 1969, machine intelligence 5." Edinburgh: Edinburgh University 2 (1948).

link

Turing, Alan M. "Practical forms of type theory." The Journal of Symbolic Logic 13.02 (1948): 80-94.

Turing, Alan M. "Computing machinery and intelligence." Mind (1950): 433-460.

link

Turing, Alan M. "The word problem in semi-groups with cancellation." Annals of Mathematics (1950): 491-505.

Turing, Alan M. "THE CHEMICAL BASIS OF MORPHOGENESIS." Philosophical Transactions of the Royal Society of London. Series B, Biological Sciences 237.641 (1952): 37-72.

link

Turing, Alan M. "Chess." Computer chess compendium. Springer New York, 1988. 14-17.

This article is a reprint of pages 286-295 from

B.V. Bowden ( ed.) Faster Than Thought (A Symposium on Digital Computing Machines) Sir Isaac Pitman & Sons Ltd. 1953.

The original book in text and pdf form may be found here

Turing, Alan M. "Solvable and unsolvable problems." Science News-ens. fr 39 (1954).

link

A paper by     Verónica Bechera, Santiago Figueiraa  and  Rafael Picchia  presenting the unpublished work of Turing in normal numbers

Becher, Verónica, Santiago Figueira, and Rafael Picchi. "Turing’s unpublished algorithm for normal numbers." Theoretical Computer Science 377.1 (2007): 126-138.

link

Turing, Alan M.. AM Turing's Original Proposal for the Development of an Electronic Computer: Reprinted with a Foreword by DW Davies. National Physical Laboratory, Division of Computer Science, 1972.

Turing, Alan M. "Proposal for development in the mathematics division of an automatic computing engine (ace)." Carpenter, BE, Doran, RW (eds) 46 (1986).

Turing, Alan M. "Checking a large routine." The early British computer conferences. MIT Press, 1989.

 
The next should be an anecdote; it is not. In the link below of the article written by Simone Santini, you may read some negative reviews that some incredible reviewers gave to some of the most important papers ever written. One of this papers is Turing's most famous paper.
link

Building spatial algorithms with ModelBuilder of ArcGIS

ModelBuilder of ArcGIS is the most useful tool (or set of tools) I have ever used as a GIS programmer and administrator. The main reason of course is the (very) large set of tools that comes with it. We may not overlook the simplicity in the designing of custom models; the users draw graphically a chart flow of the procedure they want to run and they run it. Moreover, if you get familiar with ModelBuilder you end up building models that you use everyday automating large parts of your daily routine work.

Most people use ModelBuilder as an application for building procedures that simply combine tools from the ArcGIS Toolkit mainly for the manipulation of spatial datasets. This is also how most tutorials describe the use of ModelBuilder, but this alone is not very interesting. Let us see through examples how a user may use ModelBuilder in order to implement spatial algorithms. A theoretical and application-independent justification of the following examples may be found in my paper here. The paper is too technical and theoretical and some people have difficulties reading it so let us see some examples of spatial algorithms implementations in ModelBuilder along with a graphical presentation of each one.

For the next examples we call N a dataset of linear features (arcs) that represent some directed network. The features are categorized in 2 or more categories and the categorization is stored in the attributed of each arcs. N is stored in a geodatabase with spatial indexes but without built topology or any network dataset relationships. One advantage of the next examples is that the user is not require to build topology or other relationships which makes the procedure more efficient.

Problem I: Locate the nodes in N with degree equal to one.

It is a simple problem; in each nodes of degree one (also called free node) there is only one arc attached. These nodes are the ends of dead-end streets in road networks or the terminals in telecommunication networks.

Algorithm I:

1. Create point feature class Point_1 with the endpoints of the arcs in N. Use FeatureVerticesToPoints with the option BOTH_ENDS.

2. Execute Spatial Join, set Point_1 as Join Feature and Target Featureas well. Output the result in class Point_2.

3. Select features from Point_2 where field Join_Count = 1. Output the result in class RESULT; this is the output of the algorithm.

The model runs fast as it performs spatial join among point features and it avoids computing intersections among arcs which is more complex. I have tested it in ArcGIS 10 in a network of 1,000,000 arcs. It ran in less than 5 minutes in a computer of medium capabilities.

Problem II: Locate in N the intersections of arcs that belong in categories 1 and 2.

This is a little more interesting. It is useful when you need to check the connectivity of the network as well as illegal connections. In case category 1 regards highway roads and category 2 unpaved roads, it is critical to know if there are intersections among the features of these two categories in your dataset

Algorithm II:

1. Create classes Cat_1 and Cat_2 using Select tool with the features of categories 1 and 2.

2. Create point feature classes Point_1 and Point_2 with the endpoints of the arcs of the two categories as in Algorithm I.

3. Execute Spatial Join, set Point_1 as Join feature class and Point_2 as Target. Output the result in class JOIN_RESULT.

4. Select the features from JOIN_RESULT where Join_Count > 0. Output the result in class RESULT; this is the output of the algorithm.

Problem III: Locate the points of no flow in N.

Locate the nodes in N which stand as barriers for network flow. In these nodes, network traffic is either only directed to them or only directed form them. See an instance in the following image.

Algorithm III:

1. Create point feature class Point_1 with the starting endpoints of the arcs. Use FeatureVerticesToPoints with the option END.

2. Create point feature class Point_2 with the ending endpoints of the arcs. Use FeatureVerticesToPoints with the option START.

3. Execute Spatial Join, set Point_1 as Join feature class and Point_2 as Target. Output the result in class JOIN_RESULT.

4. Select the features from JOIN_RESULT where Join_Count = 0. Output the result in class RESULT; this is the output of the algorithm.

The main idea in Algorithm 3 is that in nodes with normal flow, there is at least an ending point of an arc that leads the traffic to the node and at least a starting point of an arc that takes the traffic from it.

How to reduce a spatial problem to an easier one

The reduction of the computation of a problem A to the computation of an easier problem B is a traditional method of building a more efficient algorithm for the resolution of A, especially useful when A is computationally hard. This method is efficient when it comes to spatial analysis and spatial query problems.

Spatial query problems regard the spatial relationships of some set of objects S in a dataset E with some other set of objects S’ in dataset E’. Of course E and E’ may be the same set and in this case we talk about detection of spatial autocorellation or of overlapping features in E. One reason why such problems are sometimes hard to solve, especially for large datasets, is the nature of the spatial objects. More complex spatial objects require more complex spatial queries. The complexity of a spatial object is proportional to its dimensions and geometry.

In a paper of mine that you may find in arxiv.org here I discuss a method that I have developed to work around this issue and it has been very useful to me in GIS applications. I call this method Geometrical Reduction. It is based in the notion of mapping reduction and it regards the reduction of the computation of a spatial query in dataset E to the computation of a spatial query in dataset J where the objects in J have simpler geometry than those in E. When applied in GIS, it is required to produce dataset J analyzing the geometry of the objects in E. 

For instance, if the objects in E are polygons then J may consist of lines produced from the edges of the polygons. Then the problem of detection of overlapping edges in E is reduced to the problem of intersecting lines in J.

Next, let us define which reductions are valid between object classes.

Geometrical Reduction of object classes

A computable function g reduces geometrically n-dimensional object class A to d-dimensional object class B, A ≤_G B, if for every object o in A <=> object g(o) in B.

Then Geometrical Reduction is defined as follows.

Geometrical Reduction of spatial relationships

Spatial relationship S(A, C) is geometrically reducible to spatial relationship P(B, D), written S(A, C) ≤_G P(B, D), if A ≤_G B and C ≤_G D and if S(A, C) is satisfied when P(B, D) is satisfied and P(B, D) is satisfied when S(A, C) is satisfied.

Geometrical reduction theorem

The problem R of deciding if a spatial relationship P(B, D) is valid in dataset E is mapping reducible to problem V of deciding if a spatial relationship S(A, C) is valid in dataset J, if P(B, D) ≤_G S(A, C) and if there is a computable function h that decides V.

In my paper I study the problem of detection of connection errors in networks of linear features and especially in hierarchical networks and I use geometrical reduction in order to build efficient algorithms even for large datasets.