Wyniki wyszukiwania - BazTech

1

On Completeness of Cost Metrics and Meta-Search Algorithms in $-Calculus

Eberbach Eugene

Fundamenta Informaticae

|

2022

|

Vol. 188 nr 2

63--90

EN

In the paper we define three new complexity classes for Turing Machine undecidable problems inspired by the famous Cook/Levin's NP-complete complexity class for intractable problems. These are U-complete (Universal complete), D-complete (Diagonalization complete) and H-complete (Hypercomputation complete) classes. In the paper, in the spirit of Cook/Levin/Karp, we started the population process of these new classes assigning several undecidable problems to them. We justify that some super-Turing models of computation, i.e., models going beyond Turing machines, are tremendously expressive and they allow to accept arbitrary languages over a given alphabet including those undecidable ones. We prove also that one of such super-Turing models of computation - the $-Calculus, designed as a tool for automatic problem solving and automatic programming, has also such tremendous expressiveness. We investigate also completeness of cost metrics and meta-search algorithms in $-calculus.

2

Q∖Z is diophantine over Q with 32 unknowns

Zhang Geng-Rui, Sun Zhi-Wei

Bulletin of the Polish Academy of Sciences. Mathematics

|

2022

|

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.

3

One Henkin Quantifier in the Empty Vocabulary Suffices for Undecidability

Zdanowski Konrad

Fundamenta Informaticae

|

2019

|

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).

4

Pure Strategies in Imperfect Information Stochastic Games

Carayol A., Löding C., Serre O.

Fundamenta Informaticae

|

2018

|

Vol. 160, nr 4

361--384

EN

We consider imperfect information stochastic games where we require the players to use pure (i.e. non randomised) strategies. We consider reachability, safety, Büchi and co-Büchi objectives, and investigate the existence of almost-sure/positively winning strategies for the first player when the second player is perfectly informed or more informed than the first player. We obtain decidability results for positive reachability and almost-sure Büchi with optimal algorithms to decide existence of a pure winning strategy and to compute one if it exists. We complete the picture by showing that positive safety is undecidable when restricting to pure strategies even if the second player is perfectly informed.

5

Small Semi-Thue System Universal with Respect to the Termination Problem

Halava V., Matiyasevich Y., Niskanen R.

Fundamenta Informaticae

|

2017

|

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.

6

On Hypercomputation, Universal and Diagonalization Complete Problems

Eberbach E.

Fundamenta Informaticae

|

2015

|

Vol. 139, nr 4

329--346

EN

In the paper we define the class of hypercomputation complete and hard undecidable problems. We prove that typical unsolvable problems are decidable in infinity. We hypothesize that all undecidable problems can be reduced in infinity to each other, i.e., they are H-complete (hypercomputation complete). We propose also two other classes: U-complete (universal complete) and D-complete (diagonalization complete) that use asymptotic reduction and allow separate non- RE and RE non-recursive undecidable classes.

7

Decision Problems for Probabilistic Finite Automata on Bounded Languages

Bell P. C., Halava V., Hirvensalo M.

Fundamenta Informaticae

|

2013

|

Vol. 123, nr 1

1--14

EN

We show that several problems concerning probabilistic finite automata of a fixed dimension and a fixed number of letters for bounded cut-point and strict cut-point languages are algorithmically undecidable by a reduction of Hilbert’s tenth problem. We then consider the set of so called “F-Problems” (emptiness, infiniteness, containment, disjointness, universe and equivalence) and show that they are also undecidable for bounded (non-)strict cut-point languages on probabilistic finite automata. For a finite set of matrices { M1 , M2 , . . . , Mk }⊆ Q txt , we then consider the decidability of computing the maximal spectral radius of any matrix in the set X = { Mj11 Mj22··· Mjkk|j1, j2, . . . , jk≥0 } , which we call a bounded matrix language. Using an encoding of a probabilistic finite automaton shown in the paper, we prove the surprising result that determining if the maximal spectral radius of a bounded matrix language is less than or equal to one is undecidable, but determining whether it is strictly less than one is in fact decidable (which is similar to a result recently shown for quantum automata).

8

A Note on Two-pebble Automata Over Infinite Alphabets

Kaminski M., Tan T.

Fundamenta Informaticae

|

2010

|

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.

9

A Note on the Emptiness of Semigroup Intersections

Bell P.

Fundamenta Informaticae

|

2007

|

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.

10

Undecidability in w-Regular Languages

Halava V., Harju T., Karhumäki J.

Fundamenta Informaticae

|

2006

|

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.