PL
 |
EN
Nowa wersja platformy, zawierająca wyłącznie zasoby pełnotekstowe, jest już dostępna.
Przejdź na https://bibliotekanauki.pl
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 9

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  undecidability
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote A Note on Two-pebble Automata Over Infinite Alphabets
100%
Kaminski M. , Tan T.
|
2010
|
tom Vol. 98, nr 4
379-390
EN
It is shown that the emptiness problemfor two-pebble automata languages is undecidable and that two-pebble automata are weaker than three-pebble automata.
2
Content available remote A Note on the Emptiness of Semigroup Intersections
100%
Bell P.
|
2007
|
tom Vol. 79, nr 1-2
1-4
EN
We consider decidability questions for the emptiness problem of intersections of matrix semigroups. This problem was studied by A. Markov [7] and more recently by V. Halava and T. Harju [5]. We give slightly strengthened results of their theorems by using a different matrix encoding. In particular, we show that given two finitely generated semigroups of non-singular upper triangular 3 ×3 matrices over the natural numbers, checking the emptiness of their intersections is undecidable. We also show that the problem is undecidable even for unimodular matrices over 3 ×3 rational matrices.
3
Content available remote Small Semi-Thue System Universal with Respect to the Termination Problem
100%
Halava V. , Matiyasevich Y. , Niskanen R.
Fundamenta Informaticae
|
2017
|
tom Vol. 154, nr 1/4
177--184
EN
The termination problem for semi-Thue systems asks whether all derivations for a given word in a given semi-Thue system are finite, i.e., all derivations terminate after finite number of steps. This problem is known to be undecidable, there is a standard reduction of the halting problem of the Turing machines into termination problem; moreover, one can fix a semi-Thue system and still have the undecidability. In 1996 Sénizergues and the second author gave a construction for a 3-rule semi-Thue system with undecidable termination problem. However, in their construction the words of one of the rules are very long. Using some ideas of Tseijtin we give a construction for a semi-Thue system with low number of short rules having undecidable termination problem. Namely, we construct a semi-Thue system with 24 rules over 8 letter alphabet with rule words of length at most 5, and the termination problem for this semi-Thue system is undecidable. Moreover, this system is universal, that is, it can simulate any semi-Thue system.
4
Content available remote One Henkin Quantifier in the Empty Vocabulary Suffices for Undecidability
100%
Zdanowski K.
|
2019
|
tom Vol. 164, nr 4
375--386
EN
We prove that there are single Henkin quantifiers such that first order logic augmented by one of these quantifiers is undecidable in the empty vocabulary. We estimate the size of such quantifiers proving undecidability of Lø(H12) and Lø(E10).
5
Content available remote Q∖Z is diophantine over Q with 32 unknowns
88%
Zhang G.-R. , Sun Z.-W.
Bulletin of the Polish Academy of Sciences. Mathematics
|
2022
|
tom Vol. 70, no. 2
93--106
EN
In 2016 J. Koenigsmann refined a celebrated theorem of J. Robinson by proving that Q∖Z is diophantine over Q, i.e., there is a polynomial P(t,x1,…,xn)∈Z[t,x1,…,xn] such that for any rational number t we have t/∈Z⟺∃x1⋯∃xn [P(t,x1,…,xn)=0], where variables range over Q, equivalently t∈Z⟺∀x1⋯∀xn [P(t,x1,…,xn)/=0]. In this paper we prove that we may take n=32. Combining this with a result of Z.-W. Sun, we show that there is no algorithm to decide for any f(x1,…,x41)∈Z[x1,…,x41] whether ∀x1⋯∀x9∃y1⋯∃y32 [f(x1,…,x9,y1,…,y32)=0], where variables range over Q.
6
More on The Decidability of Mereological Theories
88%
Tsai H.-c.
|
|
tom 20
|
nr 3
251-265
EN
Quite a few results concerning the decidability of mereological theories have been given in my previous paper. But many mereological theories are still left unaccounted for. In this paper I will refine a general method for proving the undecidability of a theory and then by making use of it, I will show that most mereological theories that are strictly weaker than CEM are finitely inseparable and hence undecidable. The same results might be carried over to some extensions of those weak theories by adding the fusion axiom schema. Most of the proofs to be presented in this paper take finite lattices as the base models when applying the refined method. However, I shall also point out the limitation of this kind of reduction and make some observations and conjectures concerning the decidability of stronger mereological theories.
7
Content available remote Undecidability in w-Regular Languages
88%
Halava V. , Harju T. , Karhumäki J.
|
2006
|
tom Vol. 73, nr 1-2
119-125
EN
In the infinite Post Correspondence Problem an instance (h,g) consists of two morphisms h and g, and the problem is to determine whether or not there exists an infinite word a such that h(a) = g(a). In the general case this problem was shown to be undecidable by K. Ruohonen (1985). Recently, it was proved that the infinite PCP is undecidable already when the domain alphabet of the morphisms consists of at least 9 letters. Here we show that the problem is undecidable for instances where the morphisms have a domain of 6 letters, when we restrict to solutions of w-languages of the form Rw where R is a given regular language.
8
Content available Gödel’s Philosophical Challenge (to Turing)
75%
Sieg W.
|
|
nr 1
EN
The incompleteness theorems constitute the mathematical core of Gödel’s philosophical challenge. They are given in their “most satisfactory form”, as Gödel saw it, when the formality of theories to which they apply is characterized via Turing machines. These machines codify human mechanical procedures that can be carried out without appealing to higher cognitive capacities. The question naturally arises, whether the theorems justify the claim that the human mind has mathematical abilities that are not shared by any machine. Turing admits that non-mechanical steps of intuition are needed to transcend particular formal theories. Thus, there is a substantive point in comparing Turing’s views with Gödel’s that is expressed by the assertion, “The human mind infinitely surpasses any finite machine”. The parallelisms and tensions between their views are taken as an inspiration for beginning to explore, computationally, the capacities of the human mathematical mind.
9
Content available Stawka większa niż las
71%
Szaj P.
Annales Universitatis Paedagogicae Cracoviensis. Studia Poetica
|
2020
|
tom 8
342-355
EN
More than forest at stake [Book review – “O jeden las za daleko. Demokracja, kapitalizm i nieposłuszeństwo ekologiczne w Polsce” (A forest too far: democracy, capitalism and ecological disobedience in Poland), red. Przemysław Czapliński, Joanna B. Bednarek, Dawid Gostyński, Książka i Prasa, Warszawa 2019, ss. 365]
PL
Stawka większa niż las [Recenzja książki: „O jeden las za daleko. Demokracja, kapitalizm i nieposłuszeństwo ekologiczne w Polsce”, red. Przemysław Czapliński, Joanna B. Bednarek, Dawid Gostyński, Książka i Prasa, Warszawa 2019, ss. 365]
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.