Connections of theory of computability and Turing machines to other areas of mathematics

Question

The question is quite straightforward: Could you point out some reference papers that highlight (in a way that is fairly accessible) the connections between (1) theory of computability, algorithms, and Turing machines and (2) other areas of mathematics.

Answer 1

You can consider Computability and Complexity :

[for the] study and classification of which mathematical problems are computable and which are not. In addition, there is an extensive classification of computable problems into computational complexity classes according to how much computation — as a function of the size of the problem instance — is needed to answer that instance.

See e.g. :

• Sanjeev Arora & Boaz Barak, Computational complexity : A Modern Approach (2009)

• Pavel Pudlak, Logical Foundations of Mathematics and Computational Complexity (2013).

And also Computable Analysis i.e. :

is the study of mathematical analysis from the perspective of computability theory. It is concerned with the parts of real analysis and functional analysis that can be carried out in a computable manner.

See e.g. :

• Klaus Weihrauch, Computable Analysis : An Introduction (2000) [and also here].

Answer 2

Linear and Integer Programming utilize these a lot. I read a paper for my IP class showing that there is no algorithm to solve IPs with quadratic constraints. It was proven by a reduction to Hilbert's Tenth Problem, which is unsolvable. The reduction had a standard computability feel to it. Hilbert's Tenth Problem deals with satisfying arbitrary Diophantine equations.

Graph theory and combinatorics are the obvious places where algorithms come into play.

Game theory is really starting to benefit from computer science and algorithms. Algorithmic game theory is a very hot topic with applications to economics and AI. Computability comes up some too:
http://arxiv.org/abs/1204.0198
http://link.springer.com/article/10.1007%2FBF01212014
http://econpapers.repec.org/paper/fthcambri/153.htm