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.).},

Publication Sections

Contact | Site Map | Site powered by SPIP 3.0.26 + AHUNTSIC [CC License]

info visites 817319