Computability

We study relative precompleteness in the context of the theory of numberings, and relate this to a notion of lowness. We introduce a notion of divisibility for numberings, and use it to show that for the class of divisible numberings, lowness and relative precompleteness coincide with being computable. We also study the complexity of Skolem functions arising from Arslanov’s completeness criterion with parameters. We show that for suitably divisible numberings, these Skolem functions have the maximal possible Turing degree. In particular this holds for the standard numberings of the partial computable functions and the c.e. sets.

Anton Golov

Sebastiaan A. Terwijn

Fixpoints and relative precompleteness

不动点和相对预完备性

The complexity of equivalence relations has received much attention in the recent literature. The main tool for such endeavour is the following reducibility: given equivalence relations R and S on natural numbers, R is computably reducible to S if there is a computable function f : ω → ω that induces an injective map from R-equivalence classes to S-equivalence classes. In order to compare the complexity of equivalence relations which are computable, researchers considered also feasible variants of computable reducibility, such as the polynomial-time reducibility. In this work, we explore Peq, the degree structure generated by primitive recursive reducibility on primitive recursive equivalence relations with infinitely many equivalence classes. In contrast with all other known degree structures on equivalence relations, we show that Peq has much more structure: e.g., we show that it is a dense distributive lattice. On the other hand, we also offer evidence of the intricacy of Peq, proving, e.g., that the structure is neither rigid nor homogeneous.

Nikolay Bazhenov

Keng Meng Ng

Luca San Mauro

Andrea Sorbi

Primitive recursive equivalence relations and their primitive recursive complexity

原始递归等价关系及其原始递归复杂性

In her 1990 thesis, Ahmad showed that there is a so-called “Ahmad pair”, i.e., there are incomparable Σ 2 0 -enumeration degrees a 0 and a 1 such that every enumeration degree x &lt; a 0 is ⩽ a 1 . At the same time, she also showed that there is no “symmetric Ahmad pair”, i.e., there are no incomparable Σ 2 0 -enumeration degrees a 0 and a 1 such that every enumeration degree x 0 &lt; a 0 is ⩽ a 1 and such that every enumeration degree x 1 &lt; a 1 is ⩽ a 0 . In this paper, we first present a direct proof of Ahmad’s second result. We then show that her first result cannot be extended to an “Ahmad triple”, i.e., there are no Σ 2 0 -enumeration degrees a 0 , a 1 and a 2 such that both ( a 0 , a 1 ) and ( a 1 , a 2 ) are an Ahmad pair. On the other hand, there is a “weak Ahmad triple”, i.e., there are pairwise incomparable Σ 2 0 -enumeration degrees a 0 , a 1 and a 2 such that every enumeration degree x &lt; a 0 is also ⩽ a 1 or ⩽ a 2 ; however neither ( a 0 , a 1 ) nor ( a 0 , a 2 ) is an Ahmad pair.

Jun Le Goh

Steffen Lempp

Mariya I. Soskova

Extensions of two constructions of Ahmad

Ahmad两种构造的扩展

In this paper, we study Hausdorff and Fourier dimension from the point of view of effective descriptive set theory and Type-2 Theory of Effectivity. Working in the hyperspace K ( X ) of compact subsets of X, with X = [ 0 , 1 ] d or X = R d , we characterize the complexity of the family of sets having sufficiently large Hausdorff or Fourier dimension. This, in turn, allows us to show that family of all the closed Salem sets is Π 3 0 -complete. One of our main tools is a careful analysis of the effectiveness of a classical theorem of Kaufman. We furthermore compute the Weihrauch degree of the functions computing Hausdorff and Fourier dimension of closed sets.

Alberto Marcone

Manlio Valenti

Effective aspects of Hausdorff and Fourier dimension

Hausdorff维数与Fourier维数的有效方面

In this article, we study a notion of the extraction rate of Turing functionals that translate between notions of randomness with respect to different underlying probability measures. We analyze several classes of extraction procedures: (1) a class that generalizes von Neumann’s trick for extracting unbiased randomness from the tosses of a biased coin, (2) a class based on work of by Knuth and Yao (which more properly can be characterized as extracting biased randomness from unbiased randomness), and (3) a class independently developed by Levin and Kautz that generalizes the data compression technique of arithmetic coding. For the first two classes of extraction procedures, we identify a level of algorithmic randomness for an input that guarantees that we attain the extraction rate along that input, while for the third class, we calculate the rate attained along sufficiently random input sequences.

Douglas Cenzer

Christopher P. Porter

Randomness extraction in computability theory

计算理论中的随机性提取

Cops and robbers is a vertex pursuit game played on connected reflexive graphs. While the game is most often played with a single cop on a finite graph, we consider the variation in which n cops pursue the robber on an infinite graph. For each n ⩾ 2, we show there is a computable graph which is classically cop-win and can be won by n cops using a computable strategy, but cannot be won by n − 1 cops using a computable strategy. Furthermore, we show that the index set of n-cop-win computable graphs is Π 1 1 -complete.

Alexa McLeod

Reed Solomon

Computing strategies for multiple cops on infinite graphs

无限图上多个警察的计算策略

A semi-conditional grammar, introduced by Gheorghe Păun, is a form of regulated rewriting system where each rule consists of a context-free core rule A → w along with two strings w + , w − . The rule is applicable if w + (the positive condition) occurs as a substring of the current sentential form, but w − (the negative condition) does not. The maximum lengths i, j of the positive or negative conditional strings, respectively, give a natural measure of descriptional complexity, known as the degree of such grammars. Employing several normal form results on phrase-structure grammars as derived in particular by Viliam Geffert, we improve on previously obtained results by reducing the number of nonterminals of semi-conditional grammars of a given degree ( i , j ) while maintaining computational completeness of the said mechanisms.

Henning Fernau

Lakshmanan Kuppusamy

Rufus O. Oladele

On the computational completeness of several descriptional complexity restrictions of semi-conditional grammars

关于半条件文法几种描述复杂性限制的计算完备性

The analogue of Hilbert’s 10th Problem for a first-order structure A with signature L asks whether there exists an algorithm that given an L-sentence of the form ∃ x → [ s = t ] decides whether ∃ x → [ s = t ] is true in A. In this paper, we consider term algebras over a finite signature with at least one constant symbol and one function symbol of arity at least two. We investigate the structure we obtain by extending the term algebra with a substitution operator. We prove undecidability of the analogue of Hilbert’s 10th problem without relying on the solution to the original Hilbert’s 10th Problem.

Juvenal Murwanashyaka

Hilbert’s tenth problem for term algebras with a substitution operator

带替换算子的项代数的希尔伯特第十问题

We explore Solovay reducibility in the context of computably approximable reals, extending its natural characterization for left-c.e. reals via computable Lipschitz functions. Our paper offers two distinct characterizations: the first employs Lipschitz functions, while the second utilizes Turing reductions with bounded use with respect to signed-digit representation. Additionally, we examine multiple related reducibilities and establish separations among them. These results contribute to a refined perspective of the relationship between Solovay reducibility and computable Lipschitz functions.

Masahiro Kumabe

Kenshi Miyabe

Toshio Suzuki

Solovay reducibility via Lipschitz functions and signed-digit representation

通过Lipschitz函数和有符号数字表示的Solovay可约性

We consider the length of the longest word definable in FO and MSO via a formula of size n. For both logics we obtain as an upper bound for this number an exponential tower of height linear in n. We prove this by counting types with respect to a fixed quantifier rank. As lower bounds we obtain for both FO and MSO an exponential tower of height in the order of a rational power of n. We show these lower bounds by giving concrete formulas defining word representations of levels of the cumulative hierarchy of sets. For the two-variable fragment of FO we obtain quadratic lower and upper bounds for the definability numbers of quantifier rank k fragments. In addition, we consider the Löwenheim–Skolem and Hanf numbers of these logics on words and obtain similar bounds for these as well.

Lauri Hella

Miikka Vilander

Defining long words succinctly in FO and MSO

在FO和MSO中简洁定义长单词

Abbreviation
Journal Impact	0.28
Quartiles(Global)	MATHEMATICS, APPLIED(Q4)

ISSN	2211-3568, 2211-3576
h-index	12

Publication Information	Publisher: IOS Press BV，Publishing cycle: ，Journal Type: journal，Open Access Journals: No
Basic data	Year of publication: 2012，Proportion of original research papers: 100.00%，Self Citation Rate:0.00%， Gold OA Rate: 0.00%

Computability

Journal Citation Format

A journal article with 1 author

A journal article with 2 authors

A journal article with 3 authors

A journal article with 5 or more authors

Books Citation Format

Thesis Citation Format

Web sites Citation Format

Patent Citation Format

Staying up late manually editing references? ivySCI automatically matches journals and helps you generate references with a single click.

Share Submission Experience