Lógica de computabilidade

Introduzida por Giorgi Japaridze em 2003, lógica de computabilidade é um programa de pesquisa e quadro matemático para reabilitação lógica como uma Teoria da Computabilidade formal sistemática, ao contrário da lógica clássica, a qual é uma teoria formal de prova. Nessa abordagem, fórmulas lógicas representam problemas computacionais (ou, equivalentemente, capacidades computacionais), e sua validade significa ser “sempre computável”.

Problemas e capacidades computacionais são compreendidas em seus sensos mais geral-interativos. Eles são formalizados como jogos entre a máquina e o seu meio, e computabilidade refere-se à existência de uma máquina que vença o jogo, qualquer que seja o comportamento do ambiente. Definindo o que seriam máquinas jogadoras, a lógica de computabilidade provê a generalização da Tese de Church-Turing para o nível interativo.

O conceito clássico de verdade acaba se tornando^[^{carece de fontes?]} uma caso especial de computabilidade, a Interatividade de Grau Zero. Isso faz da lógica clássica um fragmento especial da lógica de computabilidade. Sendo uma extensão conservadora do padrão, lógica de computabilidade é, ao mesmo tempo, pela ordem de magnitude mais expressiva, construtiva e computacionalmente significativa. Fornecendo uma resposta sistemática para a questão fundamental “quem (e como) pode ser computado?”, isso tem uma vasta gama de potenciais áreas de aplicação. Isso inclui teorias aplicadas construtivas, sistemas com base de conhecimento, sistemas de planejamento e ação.

Por trás da lógica clássica, lógica linear (compreendida em um senso simples) e lógica intuitiva também acabam se tornando fragmentos naturais do lógica de computabilidade. Logo, conceitos significativos de “verdade intuitiva” e “verdade de lógica linear” pode ser derivada a partir da semântica da lógica de computabilidade.

Sendo semanticamente construído, a lógica de computabilidade ainda não tem uma teoria de prova completamente desenvolvida. Encontrar sistemas dedutivos para fragmentos variados disso e explorar sua propriedades sintáticas é uma área de pesquisa em andamento.

Ver também[editar | editar código-fonte]

Referências

G. Japaridze, Introduction to computability logic. Annals of Pure and Applied Logic 123 (2003), pages 1–99.
G. Japaridze, Propositional computability logic I. ACM Transactions on Computational Logic 7 (2006), pages 302-330.
G. Japaridze, Propositional computability logic II. ACM Transactions on Computational Logic 7 (2006), pages 331-362.
G. Japaridze, Introduction to cirquent calculus and abstract resource semantics. Journal of Logic and Computation 16 (2006), pages 489-532.
G. Japaridze, Computability logic: a formal theory of interaction. Interactive Computation: The New Paradigm. D.Goldin, S.Smolka and P.Wegner, eds. Springer Verlag, Berlin 2006, pages 183-223.
G. Japaridze, From truth to computability I. Theoretical Computer Science 357 (2006), pages 100-135.
G. Japaridze, From truth to computability II. Theoretical Computer Science 379 (2007), pages 20–52.
G. Japaridze, Intuitionistic computability logic. Acta Cybernetica 18 (2007), pages 77–113.
G. Japaridze, The logic of interactive Turing reduction. Journal of Symbolic Logic 72 (2007), pages 243-276.
G. Japaridze, The intuitionistic fragment of computability logic at the propositional level. Annals of Pure and Applied Logic 147 (2007), pages 187-227.
G. Japaridze, Cirquent calculus deepened. Journal of Logic and Computation 18 (2008), No.6, pp. 983–1028.
G. Japaridze, Sequential operators in computability logic^{[ligação inativa]}. Information and Computation 206 (2008), No.12, pp. 1443–1475.
G. Japaridze, Many concepts and two logics of algorithmic reduction. Studia Logica 91 (2009), No.1, pp. 1–24.
G. Japaridze, In the beginning was game semantics. Games: Unifying Logic, Language and Philosophy. O. Majer, A.-V. Pietarinen and T. Tulenheimo, eds. Springer 2009, pp. 249–350.
G. Japaridze, Towards applied theories based on computability logic. Journal of Symbolic Logic 75 (2010), pp. 565–601.
I. Mezhirov and N. Vereshchagin, On abstract resource semantics and computability logic. Journal of Computer and System Sciences 76 (2010), pp. 356–372.
N. Vereshchagin, Japaridze's computability logic and intuitionistic propositional calculus. Moscow State University, 2006.

Ligações externas[editar | editar código-fonte]