THE LOGIC OF INTERACTIVE TURING REDUCTION.
The paper gives a soundness and completeness proof for the implicative fragment of intuitionistic calculus with respect to the semantics of computability logic, which understands intuitionistic implication as interactive algorithmic reduction. This concept -- more precisely, the associated concept o...
| Publicado en: | Journal of Symbolic Logic Vol. 72; no. 1; pp. 243 - 277 |
|---|---|
| Autor principal: | |
| Formato: | Artículo |
| Publicado: |
Cambridge University Press
Mar2007
|
| Materias: | |
| Acceso en línea: | Ver este registro en EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=24665167&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 24665167 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00224812 3TY jtl: Journal of Symbolic Logic issn: 00224812 maglogo: N pubinfo: dt: Mar2007 vid: 72 iid: 1 pid: 15979 pub: Cambridge University Press artinfo: ui: 24665167 10.2178/jsl/1174668394 ppf: 243 ppct: 34 formats: tig: atl: THE LOGIC OF INTERACTIVE TURING REDUCTION. aug: au: Japaridze, Giorgi affil: Department of Computing Sciences, Villanova University, 800 Lancaster Avenue, Villanova, PA 19085, USA su: Intuitionistic mathematics Game-theoretical semantics Turing (Computer program language) Mathematical logic Combinatory logic Kripke, Saul A., 1940-2022 Computational mathematics Threshold logic sug: subj: Intuitionistic mathematics Game-theoretical semantics Turing (Computer program language) Mathematical logic Combinatory logic Kripke, Saul A., 1940-2022 Computational mathematics Threshold logic keyword: Computability logic Game semantics Interactive computation Intuitionistic logic ab: The paper gives a soundness and completeness proof for the implicative fragment of intuitionistic calculus with respect to the semantics of computability logic, which understands intuitionistic implication as interactive algorithmic reduction. This concept -- more precisely, the associated concept of reducibility -- is a generalization of Turing reducibility from the traditional, input/output sorts of problems to computational tasks of arbitrary degrees of interactivity. pubtype: Academic Journal doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2007 holdings: @attributes: islocal: N |
|---|