<!DOCTYPE html><HTML lang="en"> <head><meta charset="utf-8"> <title>Williamson (Timothy) - Some Computational Constraints in Epistemic Logic (Theo Todman's Book Collection - Paper Abstracts) </title> <link href="../../TheosStyle.css" rel="stylesheet" type="text/css"><link rel="shortcut icon" href="../../TT_ICO.png" /></head> <BODY> <CENTER> <div id="header"><HR><h1>Theo Todman's Web Page - Paper Abstracts</h1><HR></div><A name="Top"></A> <TABLE class = "Bridge" WIDTH=950> <tr><th><A HREF = "../../PaperSummaries/PaperSummary_07/PaperSummary_7672.htm">Some Computational Constraints in Epistemic Logic</A></th></tr> <tr><th><A HREF = "../../Authors/W/Author_Williamson (Timothy).htm">Williamson (Timothy)</a></th></tr> <tr><th>Source: Website</th></tr> <tr><th>Paper - Abstract</th></tr> </TABLE> </CENTER> <P><CENTER><TABLE class = "Bridge" WIDTH=400><tr><td><A HREF = "../../PaperSummaries/PaperSummary_07/PaperSummary_7672.htm">Paper Summary</A></td><td><A HREF="#ColourConventions">Text Colour-Conventions</a></td></tr></TABLE></CENTER></P> <hr><P><FONT COLOR = "0000FF"><U>Author s Abstract</U><FONT COLOR = "800080"><ol type="1"><li>Some systems of <a name="1"></a><A HREF="../../Notes/Notes_1/Notes_121.htm">modal logic</A><SUP>1</SUP>, such as S5, which are often used as epistemic logics with the  necessity operator read as  the agent knows that , are problematic as general epistemic logics for agents whose computational capacity does not exceed that of a Turing machine because they impose unwarranted constraints on the agent s theory of non-epistemic aspects of the world, for example by requiring the theory to be decidable rather than merely recursively axiomatizable. </li><li>To generalize this idea, two constraints on an epistemic logic are formulated: <ol type="i"><li>R.E. conservativeness, that any recursively enumerable theory R in the sublanguage without the epistemic operator is conservatively extended by some recursively enumerable theory in the language with the epistemic operator which is permitted by the logic to be the agent s overall theory; </li><li>the weaker requirement of R.E. quasi-conservativeness is similar except for applying only when R is consistent. </ol></li><li>The logic S5 is not even R.E. quasiconservative; this result is generalized to many other <a name="2"></a><A HREF="../../Notes/Notes_1/Notes_121.htm">modal logics</A><SUP>2</SUP>. </li><li>However, it is also proved that the <a name="3"></a><A HREF="../../Notes/Notes_1/Notes_121.htm">modal logics</A><SUP>3</SUP> S4, GRZ and KDE are R.E. quasi-conservative and that K4, KE and the provability logic GLS are R.E. conservative. </li><li>Finally, R.E. conservativeness and R.E. quasiconservativeness are compared with related non-computational constraints. </li></ol> </FONT><hr><FONT COLOR = "0000FF"><B>Comment: </B><ul type="disc"><li>See <a name="W495W"></a><A HREF = "http://www.philosophy.ox.ac.uk/faculty/members/docs/recon.pdf" TARGET = "_top">Link</A> (Defunct) </li><li>To appear in D. Gabbay, S. Rahman, J.M. Torres and J.P. van Bendegem, eds., <em>Logic Epistemology and the Unity of Science</em>, Oxford and Paris: Hermes (Cognitive Science Series)</li></ul><BR><FONT COLOR = "0000FF"><HR></P><a name="ColourConventions"></a><p><b>Text Colour Conventions (see <A HREF="../../Notes/Notes_10/Notes_1025.htm">disclaimer</a>)</b></p><OL TYPE="1"><LI><FONT COLOR = "0000FF">Blue</FONT>: Text by me; &copy; Theo Todman, 2018</li><LI><FONT COLOR = "800080">Mauve</FONT>: Text by correspondent(s) or other author(s); &copy; the author(s)</li></OL> <BR><HR><BR><CENTER> <TABLE class = "Bridge" WIDTH=950> <TR><TD WIDTH="30%">&copy; Theo Todman, June 2007 - August 2018.</TD> <TD WIDTH="40%">Please address any comments on this page to <A HREF="mailto:theo@theotodman.com">theo@theotodman.com</A>.</TD> <TD WIDTH="30%">File output: <time datetime="2018-08-03T00:15" pubdate>03/08/2018 00:15:59</time> <br><A HREF="../../Notes/Notes_10/Notes_1010.htm">Website Maintenance Dashboard</A></TD></TR> <TD WIDTH="30%"><A HREF="#Top">Return to Top of this Page</A></TD> <TD WIDTH="40%"><A HREF="../../Notes/Notes_11/Notes_1140.htm">Return to Theo Todman's Philosophy Page</A></TD> <TD WIDTH="30%"><A HREF="../../index.htm">Return to Theo Todman's Home Page</A></TD> </TR></TABLE></CENTER><HR> </BODY> </HTML>