اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدNontrivial Turmites are Turing-universal
236
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
A Turmit is a Turing machine that works over a two-dimensional grid, that is, an agent that moves, reads and writes symbols over the cells of the grid. Its state is an arrow and, depending on the symbol that it reads, it turns to the left or to the right, switching the symbol at the same time. Several symbols are admitted, and the rule is specified by the turning sense that the machine has over each symbol. Turmites are a generalization of Langtons ant, and they present very complex and diverse behaviors. We prove that any Turmite, except for those whose rule does not depend on the symbol, can simulate any Turing Machine. We also prove the P-completeness of prediction their future behavior by explicitly giving a log-space reduction from the Topological Circuit Value Problem. A similar result was already established for Langtons ant; here we use a similar technique but prove a stronger notion of simulation, and for a more general family.
قيم البحث
اقرأ أيضاً
We describe the Turing Machine, list some of its many influences on the theory of computation and complexity of computations, and illustrate its importance.
We consider computations of a Turing machine under noise that causes consecutive violations of the machines transition function. Given a constant upper bound B on the size of bursts of faults, we construct a Turing machine M(B) subject to faults that
can simulate any fault-free machine under the condition that bursts are not closer to each other than V for an appropriate V = O(B^2).
The ACM A.M. Turing Award is commonly acknowledged as the highest distinction in the realm of computer science. Since 1960s, it has been awarded to computer scientists who made outstanding contributions. The significance of this award is far-reaching
to the laureates as well as their research teams. However, unlike the Nobel Prize that has been extensively investigated, little research has been done to explore this most important award. To this end, we propose the Turing Number (TN) index to measure how far a specific scholar is to this award. Inspired by previous works on Erdos Number and Bacon Number, this index is defined as the shortest path between a given scholar to any Turing Award Laureate. Experimental results suggest that TN can reflect the closeness of collaboration between scholars and Turing Award Laureates. With the correlation analysis between TN and metrics from the bibliometric-level and network-level, we demonstrate that TN has the potential of reflecting a scholars academic influence and reputation.
Global dynamics of a non-linear Cellular Automata is, in general irregular, asymmetric and unpredictable as opposed to that of a linear CA, which is highly systematic and tractable. In the past efforts have been made to systematize non-linear CA evol
utions in the light of Boolean derivatives and Jacobian Matrices. In this paper two different efforts have been made: first we try to systematize non-linear CA evolution in the light of deviant states and non-deviant states. For all the non-deviant states the nearest linear rule matrix is applicable where as for the deviant states we have a set of other matrices. Second using algebraic manipulation, an efficient algorithm is proposed by which every Non-linear Boolean function can be characterized by a sequence of binary matrices.
In this paper we study the family of freezing cellular automata (FCA) in the context of asynchronous updating schemes. A cellular automaton is called freezing if there exists an order of its states, and the transitions are only allowed to go from a l
ower to a higher state. A cellular automaton is asynchronous if at each time-step only one cell is updated. Given configuration, we say that a cell is unstable if there exists a sequential updating scheme that changes its state. In this context, we define the problem AsyncUnstability, which consists in deciding if a cell is unstable or not. In general AsyncUnstability is in NP, and we study in which cases we can solve the problem by a more efficient algorithm. We begin showing that AsyncUnstability is in NL for any one-dimensional FCA. Then we focus on the family of life-like freezing CA (LFCA), which is a family of two-dimensional two-state FCA that generalize the freezing version of the game of life, known as life without death. We study the complexity of AsyncUnstability for all LFCA in the triangular and square grids, showing that almost all of them can be solved in NC, except for one rule for which the problem is NP-complete.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
