Mathematical logic | Computability theory

Computability theory

Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since expanded to include the study of generalized computability and definability. In these areas, computability theory overlaps with proof theory and effective descriptive set theory. Basic questions addressed by computability theory include: * What does it mean for a function on the natural numbers to be computable? * How can noncomputable functions be classified into a hierarchy based on their level of noncomputability? Although there is considerable overlap in terms of knowledge and methods, mathematical computability theorists study the theory of relative computability, reducibility notions, and degree structures; those in the computer science field focus on the theory of subrecursive hierarchies, formal methods, and formal languages. (Wikipedia).

Video thumbnail

Sets, logic and computability | Math History | NJ Wildberger

In this video we give a very quick overview of a highly controversial period in the development of modern mathematics: the rise of set theory, logic and computability in the late 19th and early 20th centuries. Starting with the pioneering but contentious work of Georg Cantor in creating S

From playlist MathHistory: A course in the History of Mathematics

Video thumbnail

Number theory Full Course [A to Z]

Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure #mathematics devoted primarily to the study of the integers and integer-valued functions. Number theorists study prime numbers as well as the properties of objects made out of integers (for example, ratio

From playlist Number Theory

Video thumbnail

Commutative algebra 53: Dimension Introductory survey

This lecture is part of an online course on commutative algebra, following the book "Commutative algebra with a view toward algebraic geometry" by David Eisenbud. We give an introductory survey of many different ways of defining dimension. Reading: Section Exercises:

From playlist Commutative algebra

Video thumbnail

(PP 6.2) Multivariate Gaussian - examples and independence

Degenerate multivariate Gaussians. Some sketches of examples and non-examples of Gaussians. The components of a Gaussian are independent if and only if they are uncorrelated.

From playlist Probability Theory

Video thumbnail

Computability and problems with Set theory | Math History | NJ Wildberger

We look at the difficulties and controversy surrounding Cantor's Set theory at the turn of the 20th century, and the Formalist approach to resolving these difficulties. This program of Hilbert was seriously disrupted by Godel's conclusions about Inconsistency of formal systems. Nevertheles

From playlist MathHistory: A course in the History of Mathematics

Video thumbnail

Logic: The Structure of Reason

As a tool for characterizing rational thought, logic cuts across many philosophical disciplines and lies at the core of mathematics and computer science. Drawing on Aristotle’s Organon, Russell’s Principia Mathematica, and other central works, this program tracks the evolution of logic, be

From playlist Logic & Philosophy of Mathematics

Video thumbnail

Groups that commute Lesson 27

You might find that for certain groups, the commutative property hold. In this video we will assume the existence of such a group and prove a few properties that it may have, by way of some example problems.

From playlist Abstract algebra

Video thumbnail

Commutative algebra 1 (Introduction)

This lecture is part of an online course on commutative algebra, following the book "Commutative algebra with a view toward algebraic geometry" by David Eisenbud. https://link.springer.com/book/10.1007/978-1-4612-5350-1 This is a short introductory lecture, and gives a few examples of the

From playlist Commutative algebra

Video thumbnail

Galois theory: Introduction

This lecture is part of an online course on Galois theory. This is an introductory lecture, giving an informal overview of Galois theory. We discuss some historical examples of problems that it was used to solve, such as the Abel-Ruffini theorem that degree 5 polynomials cannot in genera

From playlist Galois theory

Video thumbnail

Emergent geometry: The duality between gravity and quantum field theory - Juan Maldacena

Emergent geometry: The duality between gravity and quantum field theory - Juan Maldacena Juan Maldacena Institute for Advanced Study; Faculty, School of Natural Science February 20, 2014 For more videos, visit http://video.ias.edu

From playlist Mathematics

Video thumbnail

Teena Gerhardt - 1/3 Algebraic K-theory and Trace Methods

Algebraic K-theory is an invariant of rings and ring spectra which illustrates a fascinating interplay between algebra and topology. Defined using topological tools, this invariant has important applications to algebraic geometry, number theory, and geometric topology. One fruitful approac

From playlist Summer School 2020: Motivic, Equivariant and Non-commutative Homotopy Theory

Video thumbnail

David Deutsch - Why is the Quantum so Strange?

To know reality, one must confront the quantum. It is how our world works at the deepest level. What's the quantum? It is bizarre, defying all common sense. Particles in two positions at the same time. Spooky action at a distance. It would sound absurd if it weren't true. For more on info

From playlist Closer To Truth - David Deutsch Interviews

Video thumbnail

David Deutsch - Why is the Quantum so Strange?

To know reality, one must confront the quantum. It is how our world works at the deepest level. What's the quantum? Click here to watch more interviews with David Deutsch http://bit.ly/1xAaXvW Click here to watch more interviews on quantum mechanics http://bit.ly/2yJFX1w Click here to b

From playlist Closer To Truth - David Deutsch Interviews

Video thumbnail

PiTP - High Energy scattering at strong coupling via AdS/CFT - Juan Maldacena

PiTP - High Energy scattering at strong coupling via AdS/CFT Juan Maldacena Institute for Advanced Study July 25, 2007

From playlist PiTP 2007

Video thumbnail

Computing Reality (Lecture - 01) by David B Kaplan

Nonperturbative and Numerical Approaches to Quantum Gravity, String Theory and Holography DATE:27 January 2018 to 03 February 2018 VENUE:Ramanujan Lecture Hall, ICTS Bangalore The program "Nonperturbative and Numerical Approaches to Quantum Gravity, String Theory and Holography" aims to

From playlist Nonperturbative and Numerical Approaches to Quantum Gravity, String Theory and Holography

Video thumbnail

Computational Complexity Classes, Homotopy Classes and N-machines

Examined herein is the possible correspondence between computational complexity classes in computational graphs and higher homotopy classes between computability paths via the application of two methods. The first method is the use of category theory for formalizing a model of (categorifie

From playlist Wolfram Technology Conference 2021

Video thumbnail

Tests, Games, and Martin-Lof's Meaning Explanations for Intuitionistic Type Theory - Peter Dybjer

Peter Dybjer November 30, 2012 For more videos, visit http://video.ias.edu

From playlist Mathematics

Video thumbnail

Scattering amplitude in Chern-Simons matter theories by Sachin Jain

ORGANIZERS : Pallab Basu, Avinash Dhar, Rajesh Gopakumar, R. Loganayagam, Gautam Mandal, Shiraz Minwalla, Suvrat Raju, Sandip Trivedi and Spenta Wadia DATE : 21 May 2018 to 02 June 2018 VENUE : Ramanujan Lecture Hall, ICTS Bangalore In the past twenty years, the discovery of the AdS/C

From playlist AdS/CFT at 20 and Beyond

Video thumbnail

Recent progress in multiplicative number theory – Kaisa Matomäki & Maksym Radziwiłł – ICM2018

Number Theory Invited Lecture 3.5 Recent progress in multiplicative number theory Kaisa Matomäki & Maksym Radziwiłł Abstract: Multiplicative number theory aims to understand the ways in which integers factorize, and the distribution of integers with special multiplicative properties (suc

From playlist Number Theory

Video thumbnail

Entanglement entropy and dilaton effective action

Discussion Meeting: Entanglement from Gravity(URL: http://www.icts.res.in/discussion_meeting/EG2014/) Dates: Wednesday 10 Dec, 2014 - Friday 12 Dec, 2014 Description: In the last few years, quantum entanglement considerations have led to profound insights in the connection with gravity.

From playlist Discussion Meeting: Entanglement from Gravity

Related pages

Cantor space | Word problem for groups | Word problem for semigroups | Ackermann function | Differential equation | Primitive recursive function | Analog signal processing | Computability in Europe | Countable set | Neural network | Primitive recursive arithmetic | Dynamical system | Set theory | Matiyasevich's theorem | Alonzo Church | List of undecidable problems | Effective descriptive set theory | Erlangen program | Post's theorem | Turing jump | Universal Turing machine | Group (mathematics) | Identity element | Reverse mathematics | Friedberg numbering | Uncountable set | Rice's theorem | Arithmetical hierarchy | Computability logic | Computably enumerable set | Model of computation | Analytical hierarchy | Computable function | Simple set | Formal language | Julia Robinson | Injective function | Proof theory | Maximal set | Rózsa Péter | Alfred Tarski | Many-one reduction | Alan Turing | Alpha recursion theory | Blum–Shub–Smale machine | Control theory | Mathematics | Natural number | Function (mathematics) | Kolmogorov complexity | Transcomputational problem | Theory of computation | Second-order arithmetic | Cantor's theorem | Church–Turing thesis | Computable set | Turing machine | Halting problem | Hilbert's tenth problem | Admissible numbering | Bijection | Diophantine equation | Mathematical logic | Gödel's completeness theorem | Computational complexity theory | Definable set | Goodstein's theorem | Turing degree | First-order logic | Algorithm | Computability | Recursion (computer science)