Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Logics for computability
open-in-new
<p>Logics for computability are formulations of <a href="/facts/Mathematical_logic/SaI7Y3wN">logic</a> that capture some aspect of <a href="/facts/Computability/VpnJUkPN">computability</a> as a basic notion. This usually involves a mix of special <a href="/facts/Logical_connective/VkPhUs6M">logical connectives</a> as well as a <a href="/facts/Semantics/1L4WwLAP">semantics</a> that explains how the logic is to be interpreted in a computational way. </p><p>Probably the first formal treatment of logic for computability is the <i><a href="/facts/Realizability/nheEHzf9">realizability interpretation</a></i> by <a href="/facts/Stephen_Kleene/sKSax2se">Stephen Kleene</a> in 1945, who gave an interpretation of <a href="/facts/Heyting_arithmetic/aBfjC0zg">intuitionistic number theory</a> in terms of <a href="/facts/Turing_machine/ojCtglYu">Turing machine</a> computations. His motivation was to make precise the <i><a href="/facts/BHK_interpretation/Tm5t5LaF">Heyting–Brouwer–Kolmogorov (BHK) interpretation</a></i> of intuitionism, according to which proofs of mathematical statements are to be viewed as constructive procedures. </p><p>With the rise of many other kinds of logic, such as <a href="/facts/Modal_logic/I7uXvYYT">modal logic</a> and <a href="/facts/Linear_logic/NmFxFRWh">linear logic</a>, and novel semantic models, such as <a href="/facts/Game_semantics/FJSuV3un">game semantics</a>, logics for computability have been formulated in several contexts. Here we mention two. </p>