# nLab computation

Contents

### Context

#### Computability

intuitionistic mathematics

foundations

# Contents

## Idea

A program. A construction of a term of some type. The topic of computability theory.

computability

type I computabilitytype II computability
typical domainnatural numbers $\mathbb{N}$Baire space of infinite sequences $\mathbb{B} = \mathbb{N}^{\mathbb{N}}$
computable functionspartial recursive functioncomputable function (analysis)
type of computable mathematicsrecursive mathematicscomputable analysis, Type Two Theory of Effectivity
type of realizabilitynumber realizabilityfunction realizability
partial combinatory algebraKleene's first partial combinatory algebraKleene's second partial combinatory algebra

## References

### General

On the theory of computation and introducing the notion of denotational semantics of programming languages:

• Dana S. Scott, Outline of a mathematical theory of computation, in: Proceedings of the Fourth Annual Princeton Conference on Information Sciences and Systems (1970) 169–176. [pdf, pdf]

• Dana S. Scott, Christopher Strachey, Toward a Mathematical Semantics for Computer Languages, Oxford University Computing Laboratory, Technical Monograph PRG-6 (1971) [pdf, pdf]

Textbook accounts:

• Michael Sipser, Introduction to the Theory Of Computation, 3rd ed: Cengage Learning (2012) [ISBN:978-1-133-18779-0,pdf, pdf]

An account with focus on programming languages:

An account going from classical computation to quantum computation:

### As path lifting

A conceptualization of computation as something at least close to path-lifting and/or as functors between path groupoids of topological spaces (a “semantical mapping” from an “action space” parameterizing the possible computing instructions to a “knowledge space” expressing their executions):

• Jan van Leeuwen, The Philosophy of Computation, p. xix-xxx in: Proceedings of IIT.SRC 2015 – Student Research Conference Bratislava (2015) [full proceedings: pdf, web; article: pdf; slides: pdf]

Related discussion for quantum computation, with quantum circuits regarded as paths:

Last revised on February 17, 2023 at 08:46:48. See the history of this page for a list of all contributions to it.