WEAK CARDINALITY THEOREMS.
Kummer's Cardinality Theorem states that a language A must be recursive if a Turing machine can exclude for any n words w, ¡, w one of the n + 1 possibilities for the cardinality of {w, ¡. w} ∩ A. There was good reason to believe that this theorem is a peculiarity of recursion theory: neither the Ca...
| Published in: | Journal of Symbolic Logic Vol. 70; no. 3; pp. 861 - 879 |
|---|---|
| Main Author: | |
| Format: | Article |
| Published: |
Cambridge University Press
Sep2005
|
| Subjects: | |
| Online Access: | View this record in EBSCOhost |
| fields | @attributes: recordID: 1 pdfLink: plink: https://search.ebscohost.com/login.aspx?direct=true&db=hlh&AN=18033310&site=ehost-live header: @attributes: shortDbName: hlh uiTerm: 18033310 longDbName: Humanities International Complete uiTag: AN controlInfo: bkinfo: jinfo: jid: 00224812 3TY jtl: Journal of Symbolic Logic issn: 00224812 maglogo: N pubinfo: dt: Sep2005 vid: 70 iid: 3 pid: 15979 pub: Cambridge University Press artinfo: ui: 18033310 10.2178/jsl/1122038917 ppf: 861 ppct: 18 formats: tig: atl: WEAK CARDINALITY THEOREMS. aug: au: Tantau, Till affil: Technische Universität Berlin, Germany su: Recursion theory Mathematical logic Mathematical models Computer programming Computer science Programming languages sug: subj: Recursion theory Mathematical logic Mathematical models Computer programming Computer science Programming languages ab: Kummer's Cardinality Theorem states that a language A must be recursive if a Turing machine can exclude for any n words w, ¡, w one of the n + 1 possibilities for the cardinality of {w, ¡. w} ∩ A. There was good reason to believe that this theorem is a peculiarity of recursion theory: neither the Cardinality Theorem nor weak forms of it bold for resource-bounded computational models like polynomial time. This belief may be flawed. In this paper it is shown that weak cardinality theorems hold for finite automata and also for other models. An explanation is proposed as to why recursion-theoretic and automata-theoretic weak cardinality theorems hold, but not corresponding 'middle-ground theorems': The recursion- and automata-theoretic weak cardinality theorems are instantiations of purely logical weak cardinality theorems. The logical theorems can be instantiated for logical structures characterizing recursive computations and finite automata computations. A corresponding structure characterizing polynomial time computations does not exist. pubtype: Academic Journal doctype: Article src: R language: English refInfo: copyright: @attributes: flag: Y dt: @attributes: year: 2005 holdings: @attributes: islocal: N |
|---|