In this paper, complexity of an algorithmic problem, such as the halting problem for Turing machines, is measured by the classes of automata that are necessary to solve this problem. To classify different problems wit...
详细信息
ISBN:
(纸本)1932415718
In this paper, complexity of an algorithmic problem, such as the halting problem for Turing machines, is measured by the classes of automata that are necessary to solve this problem. To classify different problems with respect to their complexity, inductive Turing machines, which extend possibilities Of Turing machines, are used. A hierarchy of inductive Turing machines generates an inductive hierarchy of algorithmic problems. Here we specifically consider algorithmic problems related to Turing machines and ala inductive Turing machines, and find a place for these problems in the inductive hierarchy of algorithmic problems.
The mortality problem for 2 Chi 2 matrices is treated from the automata theory viewpoint. This problem is shown to be closely related to the reachability problem for linear and affine automata of low dimensions. The d...
详细信息
The mortality problem for 2 Chi 2 matrices is treated from the automata theory viewpoint. This problem is shown to be closely related to the reachability problem for linear and affine automata of low dimensions. The decidability of the reachability problem is proved for some subclasses of one- dimensional affine automata.
There is a dependency between computability of algorithmic complexity and decidability of different algorithmic problems. It is known that computability of the algorithmic complexity C(x) is equivalent to decidability...
详细信息
There is a dependency between computability of algorithmic complexity and decidability of different algorithmic problems. It is known that computability of the algorithmic complexity C(x) is equivalent to decidability of the halting problem for Turing machines. Here we extend this result to the realm of superrecursive algorithms, considering algorithmic complexity for inductive Turing machines. We study two types of algorithmic complexity: recursive (classical) and inductive algorithmic complexities. Relations between these types of algorithmic complexity and decidability of algorithmic problems for Turing machines and inductive Turing machines are considered. In particular, it is demonsrated that computability of algorithmic complexity is equivalent not only to decidability of the halting problem, but also to decidability by inductive Turing machines of the first order of many other problems for Turing machines, such as: if a Turing machine computes a recursive (total) function;if a Turing machine gives no result only for n inputs;if a Turing machine gives results only for n inputs. (c) 2007 Elsevier B.V. All rights reserved.
What makes an algorithmic problem easy or hard? Many general algorithmic techniques arising from decades of research, along with the theory of NP-completeness based on reductions between hard problems, offers a good a...
详细信息
What makes an algorithmic problem easy or hard? Many general algorithmic techniques arising from decades of research, along with the theory of NP-completeness based on reductions between hard problems, offers a good answer for problems where the input is ``worst-case''. However, this theory has very little to say when the input is random, and comprises of independent samples, as is frequently the case for problems in statistics. Statistical problems seemingly go through abrupt phase transitions in complexity, from hard to easy once the number of samples crosses a threshold. Understanding this boundary between ``hard'' and ``easy'' for statistical problems is still in nascent stages. This thesis comprises recent progress in understanding these phase transitions from the lens of semidefinite programming.
In this paper, we consider a natural generalization of the concept of order of an element in a group: an element g is an element of G is said to have order k in a subgroup H of G (respectively, in a coset Hu) if k is ...
详细信息
In this paper, we consider a natural generalization of the concept of order of an element in a group: an element g is an element of G is said to have order k in a subgroup H of G (respectively, in a coset Hu) if k is the first strictly positive integer such that g(k)is an element of H (respectively, g(k)is an element of Hu). We study this notion and its algorithmic properties in the realm of free groups and some related *** positive and negative (algorithmic) results emerge in this setting. On the positive side, among other results, we prove that the order of elements, the set of orders (called spectrum), and the set of preorders (ie the set of elements of a given order) \wrt finitely generated subgroups are always computable in free and free times free-abelian groups. On the negative side, we provide examples of groups and subgroups having essentially any subset of natural numbers as relative spectrum;in particular, non-recursive and even non-recursively enumerable sets of natural numbers. Also, we take advantage of Mikhailova's construction to see that the spectrum membership problem is unsolvable for direct products of nonabelian free groups.
暂无评论