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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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.
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
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
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.
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.
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]
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ć.