@article{Mon12,
title = {Introduction \`{a} la calculabilit\'{e} },
author = {Monniaux, David},
year = {2012},
journal = {Quadrature},
pages = {17--28},
volume = {86},
team = {SYNC,PACSS},
keywords = {computable functions; turing; diophantine equations; turing machines},
classmath = {*97P20 ( ) 97F60 ( )},
category = {frmag},
zbl = {1254.97018},
pdf = {Monniaux_Quadrature2012.pdf},
abstract = {Summary: Whether or not diophantine equations (that is, polynomials equations with integer coefficients and solutions) have solutions does not seem, a priori, to be related to bugs in computer programs. Computability theory establishes such a link: a classical result is that the problem of finding out whether a system of diophantine equations has a solution is the same as determining whether the execution a computer program will eventually stop. This article introduces computability theory: the difficulty of defining the class of computable functions (primitive recursive functions are insufficient), Turing machines, the Church thesis, and classical results (Halting problem, Rice's theorem, ect.).},
}
