×

A universal inductive inference machine. (English) Zbl 0763.03023

The authors deal with a paradigm of scientific discovery defined within a first-order logical framework, based on the notion of detectability. Model theoretically a sentence \(\theta\) is detectable in a class of countable models \(\text{MOD}_{\text c}(T)\) of theory \(T\) iff both \(\theta\) and \(\neg\theta\) are equivalent over \(T\) to existential- universal sentences. The main result is a proof that for every countable first-order language thee exists a universal scientist, a scientist which solves every problem that any scientist can solve, i.e. a Turing machine \(M^ T\) equipped with oracle for \(T\) such that \(M^ T\) detects \(\theta\) in \(\text{MOD}_{\text c}(T)\) if \(\theta\) is detectable in \(\text{MOD}_{\text c}(T)\). It is shown that first-order logic is a maximal regular logic which has a universal scientist and the Löwenheim-Skolem property.

MSC:

03D10 Turing machines and related notions
03B80 Other applications of logic
03C68 Other classical first-order model theory
03B10 Classical first-order logic

References:

[1] Model theory (1973)
[2] Model theoretic logics (1985)
[3] Proceedings of the seventh international joint conference on artificial intelligence (IJCAI-81) 1 pp 446– (1981)
[4] Theory of recursive functions and effective computability (1967) · Zbl 0183.01401
[5] DOI: 10.1007/BF00269958 · doi:10.1007/BF00269958
[6] DOI: 10.1007/BF00296173 · Zbl 0668.03001 · doi:10.1007/BF00296173
[7] Proceedings of the second annual workshop on computational learning theory (1989)
[8] General characterizations of inductive inference over arbitrary sets of data presentations (1990)
[9] Proceedings of the 1988 workshop on computational learning theory (1988)
[10] Notes on hierarchies and inductive inference (1990)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.