Complexity and Computation at The New Centre
27 Nov 2015

I will be teaching a course on complexity and computation at The New Centre from January 10 to March 27. The description and registration information can be found here.
Complexity and Computation:
An Introduction to Measures, Paradigms and Programs

This seminar is an introduction to two widely popular yet often culturally misconstrued topics, complexity and computation. Why are social sciences no longer tenable without an extensive restructuring around theoretical and applied dimensions of these two subjects? Why is in the absence of a systematic engagement with the all-encompassing consequences implied by the findings and advances in computation and complexity sciences, philosophy’s regression to antediluvian platitudes inevitable? And at the same time, why should the vogue culture surrounding complexity and computation be approached with a critical vigilance and extreme caution? By presenting a survey of some of the key ideas in complexity sciences and computation which have direct implications for philosophical and political thinking, this seminar sets out to tackle and answer these questions.
The first module begins with one central question: What is meant by complexity? To answer this question, we will look at different measures of complexity, their strengths and weaknesses and how they deviate from or intersect with the commonsense concept of complexity. Subsequently, we will examine these measures in relation to two questions, ‘what is a complex structure’ and ‘what is a complex function’. This inquiry will lead us to a more fine-grained investigation of complexity in natural and socio-cultural phenomena. Complexity in the order of being and in the order of thought, dynamic systems, structural stability, statistical complexity, logical depth, hierarchies or dependency-relations, generative entrenchment, intrinsic emergence, mechanisms and functions are among the topics that will be discussed in the first module.
The second module focuses on the correlations between complexity and computation particularly in the context of computational complexity and classification of computational problems in relation to measures and hierarchies discussed in the first module. However, depending on how we answer the question of what we mean by computation, the notion of computational complexity can be approached differently. To this end, we will look into what Samson Abramsky calls the two puzzles of computation, ‘why do we compute?’ and ‘what do we compute?’. This will open a discussion on the distinctions between those paradigms of computation centered on the issue of computability and those concerning the fundamental problem of what computation is. In this respect, some of the most significant challenges to the Church-Turing thesis that underlies the current dominant paradigm of computation will be addressed. We will particularly concentrate on the recent paradigm shift in computer science toward understanding the fundamental duality of computation and the interactive nature of computing. To conclude this module, we will review the two major programs of computation established by the Church-Turing and the interactive paradigms, contrasting their capacities in engaging with the question of complexity and evaluating their scope of application. Some of the key terms covered in this module are hierarchy theorems, computational classes, intractability, computational cost, sequentiality, concurrency, algorithmic computing, interaction as computation, design vs. description and the strong informatics thesis.
Drawing on the discussions presented in the first and the second modules, the third module deals with complexity and computation in the domain of cognition, particularly in the context of the linguistic scaffolding of thinking and the computational picture of language. We will primary concentrate on how social / interpersonal interaction shapes the functional architecture of language and conceptual thinking. But the question is that what is exactly ‘social’ when we refer to social linguistic interaction. To answer this question, the social-interactive dimension of language will be introduced as a computational framework that is directly linked to the generation of semantic complexity and high-order cognitive abilities. The objective of this module is to determine what is exactly computational about social linguistic practices and how linguistic interaction generates complex cognitive abilities. To this end, we will expand on the role of computational dualities – introduced in the second module – in linguistic interaction. The point of entry to our discussion regarding the connections between computational dualities of interaction, language and cognition will be the concept of game. In line with the theme of this module, we will examine Wilfrid Sellars’s account of language as rule-governed games and Robert Brandom’s game of giving and asking for reasons in light of recent works in logic and computer science on interaction games, most notably, the works of Andreas Blass, Samson Abramsky and Jean-Yves Girard.