Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: second-order logic

Sortuj według:

Ogranicz wyniki do:

The progress of science from a computational point of view: the drive towards ever higher solvability

Marciszewski Witold

Foundations of Computing and Decision Sciences

2019

Vol. 44, No. 1

11--26

This essay's content is rendered by the titles of the successive sections. 1. Effective solvability versus intuitive solvability. — 2. Decidability, i.e. effective solvability, in predicate logic. The speedup phenomenon — 3. Contributions of the second-order logic to the problems of solvability — 4. The infinite progress of science in the light of Turing's idea of the oracle. The term "oracle" is a technical counterpart of the notion of mathematical intuition. A more detailed summary can be obtained through juxtaposing the textboxes labelled with letters A...F. Conclusion: in the progress of science an essential role is played by the feedback between intellectual intuitions (intuitive solvability) and algorithmic procedures (effective solvability).

Some fragments of second-order logic over the reals for which satisfiability and equivalence are (un)decidable

Grimson R., Kuijpers B.

Reports on Mathematical Logic

2014

Vol. 49

23--34

We consider the Σ10 -fragment of second-order logic over the vocabulary [+;x; 0; 1; <; S1; …..., Sk], interpreted over the reals, where the predicate symbols Si are interpreted as semi algebraic sets. We show that, in this context, satisfiability of formulas is decidable for the first-order THERE EXISTS-quantifier fragment and undecidable for the THERE EXISTS*FOR ALL- and FOR ALL*-fragments. We also show that for these three fragments the same (un)decidability results hold for containment and equivalence of formulas.