| Computability Logic |
Article Index for Computability |
Website Links For Computability |
Information AboutComputability Logic |
| CATEGORIES ABOUT COMPUTABILITY LOGIC | |
| logic | |
| systems of formal logic | |
|
Computational problems and resources are understood in their most general - interactive sense. They are formalized as games played by a machine against its environment, and computability means existence of a machine that wins the game against any possible behavior by the environment. Defining what such game-playing machines mean, computability logic provides a generalization of the Church-Turing Thesis to the interactive level. The classical concept of truth turns out to be a special, zero-interactivity-degree case of computability. This makes classical logic a special fragment of computability logic. Being a Conservative Extension of the former, computability logic is, at the same time, by an order of magnitude more expressive, constructive and computationally meaningful. Providing a systematic answer to the fundamental question "what (and how) can be computed?", it has a wide range of potential application areas. Those include constructive applied theories, knowledge base systems, systems for planning and action. Besides classical logic, Linear Logic (understood in a relaxed sense) and Intuitionistic Logic also turn out to be natural fragments of computability logic. Hence meaningful concepts of "intuitionistic truth" and "linear-logic truth" can be derived from the semantics of computability logic. Being semantically constructed, as yet computability logic does not have a fully developed proof theory. Finding deductive systems for various fragments of it and exploring their syntactic properties is an area of ongoing research. REFERENCES
EXTERNAL LINKS
SEE ALSO |
|
|