Search

Single-tape nondeterministic Turing machines that are allowed to replace the symbol in each tape cell only when it is scanned for the first time are also known as 1-limited automata. These devices characterize, exactly as finite automata, the class of regular languages. However, they can be extremely more succinct. Indeed, in the worst case, the size gap from 1-limited automata to one-way deterministic finite automata is double exponential.Here we introduce two restricted versions of 1-limited automata, once-marking1-limited automata and always-marking1-limited automata, and study their descriptional complexity. We prove that once-marking 1-limited automata still exhibit a double exponential size gap to one-way deterministic finite automata. However, their deterministic restriction is polynomially related in size to two-way deterministic finite automata, in contrast to deterministic 1-limited automata, whose equivalent two-way deterministic finite automata in the worst case are exponentially larger. For always-marking 1-limited automata, we prove that the size gap to one-way deterministic finite automata is only a single exponential. The gap remains exponential even in the case the given machine is deterministic.We obtain other size relationships between different variants of these machines and finite automata and we present some problems that deserve investigation. [ABSTRACT FROM AUTHOR]

ABSTRACT Currently, researchers and commercial entities worldwide are highly interested in optical wireless communication links operating in terrestrial environments. These links offer the distinct advantage of enabling high‐speed data transmission while keeping operational and installation costs low, all without requiring licensing. Free‐space optical (FSO) communication has established itself as a reliable method for delivering ultra‐high data‐rate services. However, the presence of atmospheric turbulence‐induced fading poses a significant challenge for FSO communication systems, particularly when operating over channels affected by time‐varying turbulence. The effectiveness of FSO systems is greatly influenced by atmospheric conditions in a specific area because the laser beam propagates through the atmosphere. As a consequence, this can lead to a significant degradation such as high complexity, high estimation error, and high bit error rate (BER) in the performance of FSO systems. This paper presents a stacked dual attention LSTM network with layered neural Turing machine (SDALSTM‐LaNTM) for FSO channel estimation over lognormal turbulence‐induced fading channels. In this approach, the stacked structure ensures a robust feature extraction capacity of SDALSTM and enhances its ability to capture intricate relationships among multiple atmospheric variables. After employing the stacked LSTM networks, the extracted features are combined with the augmented features obtained through the dual attention (DAttn) mechanism by concatenation. Then the LaNTM architecture used external memory to solve the channel parameter estimation problem and update new set of hidden features for estimation task. The ability to access and update memory enables the model to capture long‐term dependencies and context, making it beneficial for channel prediction in FSO systems. Presently, we are in the process of verifying the channel estimation model using measured FSO channel data. Simulation results clearly demonstrate the outstanding estimation performance of the SDALSTM‐LaNTM model in FSO systems, specifically when dealing with lognormal turbulence‐induced fading channels. Moreover, we highlight the effectiveness of the SDALSTM‐LaNTM model by conducting a comprehensive comparison with existing models, considering factors such as average capacity performance, outage probability estimation, and BER. [ABSTRACT FROM AUTHOR]

This paper presents the first functional encryption (FE) scheme for the attribute-weighted sum functionality that supports the uniform model of computation. In such an FE scheme, encryption takes as input a pair of attributes (x, z) where x is public and z is private. A secret key corresponds to some weight function f, and decryption recovers the weighted sum f(x)z. In our scheme, both the public and private attributes can be of arbitrary polynomial lengths that are not fixed at system setup. The weight functions are modelled as Logspace Turing machines . Prior schemes could only support non-uniform Logspace. The proposed scheme is proven adaptively simulation secure under the well-studied symmetric external Diffie–Hellman assumption against an arbitrary polynomial number of secret key queries both before and after the challenge ciphertext. This is the best possible security notion that could be achieved for FE. On the technical side, our contributions lie in extending the techniques of Lin and Luo [EUROCRYPT 2020] devised for indistinguishability-based payload hiding attribute-based encryption for uniform Logspace access policies and the "three-slot reduction" technique for simulation-secure attribute-hiding FE for non-uniform Logspace devised by Datta and Pal [ASIACRYPT 2021] to the context of simulation-secure attribute-hiding FE for uniform Logspace. [ABSTRACT FROM AUTHOR]

For a size parameter s : ℕ → ℕ , the Minimum Circuit Size Problem (denoted by MCSP[s(n)]) is the problem of deciding whether the minimum circuit size of a given function f : {0,1}n →{0,1} (represented by a string of length N := 2n) is at most a threshold s(n). A recent line of work exhibited "hardness magnification" phenomena for MCSP: A very weak lower bound for MCSP implies a breakthrough result in complexity theory. For example, McKay, Murray, and Williams (STOC 2019) implicitly showed that, for some constant μ1 > 0, if MCSP [ 2 μ 1 ⋅ n ] cannot be computed by a one-tape Turing machine (with an additional one-way read-only input tape) running in time N1.01, then P≠NP. In this paper, we present the following new lower bounds against one-tape Turing machines and branching programs: (1) A randomized two-sided error one-tape Turing machine (with an additional one-way read-only input tape) cannot compute MCSP [ 2 μ 2 ⋅ n ] in time N1.99, for some constant μ2 > μ1. (2) A non-deterministic (or parity) branching program of size o (N 1.5 / log N) cannot compute MKTP, which is a time-bounded Kolmogorov complexity analogue of MCSP. This is shown by directly applying the Nečiporuk method to MKTP, which previously appeared to be difficult. (3) The size of any non-deterministic, co-non-deterministic, or parity branching program computing MCSP is at least N 1.5 − o 1 . These results are the first non-trivial lower bounds for MCSP and MKTP against one-tape Turing machines and non-deterministic branching programs, and essentially match the best-known lower bounds for any explicit functions against these computational models. The first result is based on recent constructions of pseudorandom generators for read-once oblivious branching programs (ROBPs) and combinatorial rectangles (Forbes and Kelley, FOCS 2018; Viola, Electron. Colloq. Comput. Complexity (ECCC) 26, 51, 2019). En route, we obtain several related results: (1) There exists a (local) hitting set generator with seed length O ~ (N) secure against read-once polynomial-size non-deterministic branching programs on N-bit inputs. (2) Any read-once co-non-deterministic branching program computing MCSP must have size at least 2 Ω ~ (N) . [ABSTRACT FROM AUTHOR]

The outputs of a Turing machine are not revealed for inputs on which the machine fails to halt. Why is an observer not allowed to see the generated output symbols as the machine operates? Building on the pioneering work of Mark Burgin, we introduce an extension of the Turing machine model with a visible output tape. As a subtle refinement to Burgin's theory, we stipulate that the outputted symbols cannot be overwritten: at step i, the content of the output tape is a prefix of the content at step j, where i < j . Our Refined Burgin Machines (RBMs) compute more functions than Turing machines, but fewer than Burgin's simple inductive Turing machines. We argue that RBMs more closely align with both human and electronic computers than Turing machines do. Consequently, RBMs challenge the dominance of Turing machines in computer science and beyond. [ABSTRACT FROM AUTHOR]

We inquire into the role of Turing's biological thought in the development of his concept of intelligent machinery. We trace the possible relations between his proto-connectionist notion of 'organising' machines in Turing (1948) on the one hand and his mathematical theory of morphogenesis in developmental biology (1952) on the other. These works were concerned with distinct fields of inquiry and followed distinct paradigms of biological theory, respectively postulating analogues of Darwinian selection in learning and mathematical laws of form in organic pattern formation. Still, these strands of Turing's work are related, first, in terms of being amenable in principle to his (1936) computational method of modelling. Second, they are connected by Turing's scattered speculations about the possible bearing of learning processes on the anatomy of the brain. We argue that these two theories form an unequal couple that, from different angles and in partial fashion, point towards cognition as a biological and embodied phenomenon while, for reasons inherent to Turing's computational approach to modelling, not being capable of directly addressing it as such. We explore ways in which these two distinct-but-related theories could be more explicitly and systematically connected, using von Neumann's contemporaneous and related work on Cellular Automata and more recent biomimetic approaches as a foil. We conclude that the nature of 'initiative' and the mode of material realisation are the key issues that decide on the possibility of intelligent machinery in Turing. [ABSTRACT FROM AUTHOR]

The descriptional complexity of basic operations on regular languages using 1-limited automata, a restricted version of one-tape Turing machines, is investigated. When simulating operations on deterministic finite automata with deterministic 1-limited automata, the sizes of the resulting devices are polynomial in the sizes of the simulated machines. The situation is different when the operations are applied to deterministic 1-limited automata: while for boolean operations the simulations remain polynomial, for product, star, and reversal they cost exponential in size. The costs for product and star do not reduce if the given machines are sweeping two-way deterministic finite automata. These bounds are tight. [ABSTRACT FROM AUTHOR]

Many models of self-assembly have been shown to be capable of performing computation. Tile Automata was recently introduced combining features of both Cellular Automata and the 2-Handed Model of self-assembly both capable of universal computation. In this work we study the complexity of Tile Automata utilizing features inherited from the two models mentioned above. We first present a construction for simulating Turing machines that performs both covert and fuel efficient computation. We then explore the capabilities of limited Tile Automata systems such as 1-dimensional systems (all assemblies are of height 1) and freezing systems (tiles may not repeat states). Using these results we provide a connection between the problem of finding the largest uniquely producible assembly using n states and the busy beaver problem for non-freezing systems and provide a freezing system capable of uniquely assembling an assembly whose length is exponential in the number of states of the system. We finish by exploring the complexity of the Unique Assembly Verification problem in Tile Automata with different limitations such as freezing and systems without the power of detachment. [ABSTRACT FROM AUTHOR]

Using assembly theory, we investigate the assembly pathways of binary strings (bitstrings) of length N formed by joining bits present in the assembly pool and the bitstrings that entered the pool as a result of previous joining operations. We show that the bitstring assembly index is bounded from below by the shortest addition chain for N, and we conjecture about the form of the upper bound. We define the degree of causation for the minimum assembly index and show that, for certain N values, it has regularities that can be used to determine the length of the shortest addition chain for N. We show that a bitstring with the smallest assembly index for N can be assembled via a binary program of a length equal to this index if the length of this bitstring is expressible as a product of Fibonacci numbers. Knowing that the problem of determining the assembly index is at least NP-complete, we conjecture that this problem is NP-complete, while the problem of creating the bitstring so that it would have a predetermined largest assembly index is NP-hard. The proof of this conjecture would imply P ≠ NP since every computable problem and every computable solution can be encoded as a finite bitstring. The lower bound on the bitstring assembly index implies a creative path and an optimization path of the evolution of information, where only the latter is available to Turing machines (artificial intelligence). Furthermore, the upper bound hints at the role of dissipative structures and collective, in particular human, intelligence in this evolution. [ABSTRACT FROM AUTHOR]

As part of ongoing research bridging ethnomethodology and computer science, in this article we offer an alternate reading of Alan Turing's 1936 paper, "On Computable Numbers". Following through Turing's machinic respecification of computation, we hope to contribute to a deflationary position on AI by showing that the activities attributed to AIs are achieved in the course of methodic hands-on work with computational systems and not in isolation by them. Turing's major innovation was a demonstration that mathematical and logical operations could be broken down into elementary, mechanically executable operations, devoid of intellectual content. Drawing out lessons from a re-enactment of Turing's methods as a means of reflecting on contemporary artificial intelligence (AI), including the way those methods disappear into the technology, we will suggest the interesting question raised in "On Computable Numbers" is less about the possibilities of designing machines that "can think" (cf. Turing, 1950), but the practical work we do, and which is made possible, when we ourselves set out to think like machines. [ABSTRACT FROM AUTHOR]

Dental cavities, caries, or tooth decay are prevalent oral health concerns worldwide. This research proposes an automated approach for dental cavities detection utilizing a Neural Turing Machines (NTM) and High Intensity Color Detection (NTM-HICD) model. These two models process the input samples in a sequence order. NTM is a type of artificial neural network (ANN) architecture that combines neural networks with external memory structures. NTM mainly designed to mimic the ability of a Turing machine to read the interesting patterns from various disease detection. The proposed NTM-HICD system combines the strengths of multiple deep learning algorithms to enhance the accuracy and robustness of dental cavity detection. The design incorporates three primary components: image processing, feature extraction, and classification. Firstly, dental X-rays are processed to enhance the quality of input data. A pre-trained model DeepLabV3+ is used to train on dental dataset. The images are then subjected to effected region extraction to focus on the tooth areas for more targeted analysis. Secondly, a set of diverse feature extraction techniques is applied to capture comprehensive information from the effected regions. Lastly, an ensemble of classifiers, such as support vector machines (SVM), random forests (RF), and deep neural networks (DNN), is employed to leverage the individual strengths of each classifier. The fusion of multiple classifiers allows for improved generalization and enhanced detection performance. [ABSTRACT FROM AUTHOR]

This document is a preface for a special issue of the journal Theory of Computing Systems. The special issue contains 7 articles that were based on extended abstracts presented at the 38th Symposium on Theoretical Aspects of Computer Science (STACS). The articles cover various areas of Theoretical Computer Science, including algorithmic graph theory, linear dynamical systems, parameterized complexity analysis, automata theory, complexity theory, algorithmic group theory, and distributed algorithms. The articles underwent a rigorous reviewing process and have been extended with additional content. The preface expresses gratitude to the authors, reviewers, and committees involved in the conference and publication process. [Extracted from the article]

The article focuses on Algebraic circuits that provide a way, alternate to Turing machines to study computation. Topics include examines the complexity classes which contain polynomial families instead of languages as it is a natural question whether an algebraic complexity class is closed under factors and this is also a useful and a very well-studied problem both from the point of view of practice and theory.

Assuming a widely believed hypothesis concerning the least prime in an arithmetic progression, we show that polynomials of degree less than n over a finite field Fq with q elements can be multiplied in time O(n logq log(n logq)), uniformly in q. Under the same hypothesis, we show how to multiply two n-bit integers in time O(n logn); this algorithm is somewhat simpler than the unconditional algorithm from the companion paper [22]. Our results hold in the Turing machine model with a finite number of tapes. [ABSTRACT FROM AUTHOR]

The article informs about the deep-rooted cybersecurity issues and the potential catastrophic consequences if not addressed, highlighting concerns in cryptocurrency, artificial intelligence, and ransomware. Topic include It proposes the recreation of a conceptual machine based on cybernetics principles to tackle these challenges, emphasizing the need for a new Turing machine and presenting five hypotheses as the foundation of this endeavor.

Alan Turing is often portrayed as a materialist in secondary literature. In the present article, I suggest that Turing was instead an idealist, inspired by Cambridge scholars, Arthur Eddington, Ernest Hobson, James Jeans and John McTaggart. I outline Turing's developing thoughts and his legacy in the USA to date. Specifically, I contrast Turing's two notions of computability (both from 1936) and distinguish between Turing's "machine intelligence" in the UK and the more well-known "artificial intelligence" in the USA. According to my proposed historical interpretation, Turing did not view computations in the real world to be exhaustively and deterministically characterized by his automatic machines from 1936. [ABSTRACT FROM AUTHOR]

There is growing evidence that many forms of neural computation may be implemented by low-dimensional dynamics unfolding at the population scale. However, neither the connectivity structure nor the general capabilities of these embedded dynamical processes are currently understood. In this work, the two most common formalisms of firing-rate models are evaluated using tools from analysis, topology, and nonlinear dynamics in order to provide plausible explanations for these problems. It is shown that low-rank structured connectivities predict the formation of invariant and globally attracting manifolds in all these models. Regarding the dynamics arising in these manifolds, it is proved they are topologically equivalent across the considered formalisms. This letter also shows that under the low-rank hypothesis, the flows emerging in neural manifolds, including input-driven systems, are universal, which broadens previous findings. It explores how low-dimensional orbits can bear the production of continuous sets of muscular trajectories, the implementation of central pattern generators, and the storage of memory states. These dynamics can robustly simulate any Turing machine over arbitrary bounded memory strings, virtually endowing rate models with the power of universal computation. In addition, the letter shows how the low-rank hypothesis predicts the parsimonious correlation structure observed in cortical activity. Finally, it discusses how this theory could provide a useful tool from which to study neuropsychological phenomena using mathematical methods. [ABSTRACT FROM AUTHOR]

Consider orbits (z , κ) of the fractal iterator f κ (z) : = z 2 + κ , κ ∈ ℂ , that start at initial points z ∈ K ̂ κ (m) ⊂ ℂ ̂ , where ℂ ̂ is the set of all rational complex numbers (their real and imaginary parts are rational) and K ̂ κ (m) consists of all such z whose complexity does not exceed some complexity parameter value m (the complexity of z is defined as the number of bits that suffice to describe the real and imaginary parts of z in lowest form). The set K ̂ κ (m) is a bounded-complexity approximation of the filled Julia set K κ . We present a new perspective on fractals based on an analogy with Chaitin's algorithmic information theory, where a rational complex number z is the analog of a program p , an iterator f κ is analogous to a universal Turing machine U which executes program p , and an unbounded orbit (z , κ) is analogous to an execution of a program p on U that halts. We define a real number Υ κ which resembles Chaitin's Ω number, where, instead of being based on all programs p whose execution on U halts, it is based on all rational complex numbers z whose orbits under f κ are unbounded. Hence, similar to Chaitin's Ω number, Υ κ acts as a theoretical limit or a "fractal oracle number" that provides an arbitrarily accurate complexity-based approximation of the filled Julia set K κ . We present a procedure that, when given m and κ , it uses Υ κ to generate K ̂ κ (m) . Several numerical examples of sets that estimate K ̂ κ (m) are presented. [ABSTRACT FROM AUTHOR]

In this article we propose an analysis of the controversy between Geoffrey Jefferson and Alan Turing in terms of a Kuhnian account of thought experiments. In this account, the main task is not to evaluate intuitions or (only) to rearrange concepts. Instead, we propose that the main task is to construct scenarios by proposing relevant experiences in which shared assumptions and conflicting lines of inquiry can be made explicit. From this perspective, we can understand the arguments and assumptions in the Jefferson-Turing thinking machine controversy [ABSTRACT FROM AUTHOR]

The evolution of universal systems has been of great interest to computer scientists. In particular, the role of Turing machines in the study of computational universality is widely recognized. Even though the patterns emerging from the evolution of this kind of dynamical system have been studied in much detail, the transition functions themselves have received less attention. In the present paper, the iota-delta function is used to encode the transition function of one-head Turing machines. In order to illustrate the methodology, we describe the transition functions of two universal Turing machines in terms of the latter function. By using the iota-delta function in this setting, Turing machines can be represented as a system of transition functions. This new representation allows us to write the transition functions as a linear combination of evolution variables wrapped by the iota-delta function. Thus, the nonlinear part of the evolution is totally described by the iota-delta function. [ABSTRACT FROM AUTHOR]

We consider the role of a Turing machine in controlling measurement experiments and the corresponding revision of Measurement Theory, incorporating the notion of physical time in a theory we show to be realised by all types of measurements of extensive quantities found in the scientific literature. Surprisingly, when we try to mechanise certain aspects of the experimental procedures with Turing machines, we uncover that quantities have an inherent measurement complexity. We demonstrate that there is a relationship between the structure of a real number and the amount of time required to measure its digits, which leads to the emergence of complexity classes associated with measuring of the digits of a real number and a new form of uncertainty: When algorithms govern experiments in Physics, then, even in the limit of the application of the theory, even in the absence of measurement errors, precise measurements of quantities cannot always be made. [ABSTRACT FROM AUTHOR]

In this work, we study two simple yet general complexity classes, based on logspace Turing machines, that provide a unifying framework for efficient query evaluation in areas such as information extraction and graph databases, among others. We investigate the complexity of three fundamental algorithmic problems for these classes: enumeration, counting, and uniform generation of solutions, and show that they have several desirable properties in this respect. Both complexity classes are defined in terms of non-deterministic logspace transducers (NL-transducers). For the first class, we consider the case of unambiguous NL-transducers, and we prove constant delay enu- meration and both counting and uniform generation of solutions in polynomial time. For the second class, we consider unrestricted NL-transducers, and we obtain polynomial delay enumeration, approximate counting in polynomial time, and polynomial-time randomized algorithms for uniform generation. More specifically, we show that each problem in this second class admits a fully polynomial-time randomized approximation scheme (FPRAS) and a polynomial-time Las Vegas algorithm (with preprocessing) for uniform generation. Remarkably, the key idea to prove these results is to show that the fundamental problem #NFA admits an FPRAS, where #NFA is the problem of counting the number of strings of length n (given in unary) accepted by a non-deterministic finite automaton (NFA). While this problem is known to be #P-complete and, more precisely, SpanL-complete, it was open whether this problem admits an FPRAS. In this work, we solve this open problem and obtain as a welcome corollary that every function in SpanL admits an FPRAS. [ABSTRACT FROM AUTHOR]

We analyze the thermodynamic cost of a logically reversible Brownian Turing machine operating in the first-passage time protocol based on the stochastic thermodynamics of resetting. In this framework, the thermodynamic cost of computation is the reset entropy production, which is interpreted as the information reduction by a resetter external to the computer. At the level of a single trajectory, the reset entropy production is associated with unidirectional transitions and is a function of the time-dependent distribution probability. We analyze an approximation that replaces the distribution probability with the empirical sojourn time, which can be obtained at the single-trajectory level. The approximation is suitable for the numerical analysis by the Gillespie algorithm and provides a reasonable average value for the reset entropy. [ABSTRACT FROM AUTHOR]

The pollution caused by aerosol (particulate matter) has a detrimental impact on urban environments, particularly in terms of socio-economic factors and public health. Aerosol particles, ranging in size from 1 nm to 100 µm, can easily penetrate organic tissues, carrying toxic gaseous compounds and minerals such as carbon monoxide, ozone, nitrogen dioxide, and sulfur dioxide. Recent advancements in neural network technology, combined with deep learning techniques, have made it possible to predict surges in aerosol pollution. In this study, we introduce DAerosol-NTM, a deep learning framework that utilizes the latest developments in neural Turing machines (NTMs) to access external memory. When compared with four baseline studies that employ multilayer perceptron (MLP), deep neural networks (DNNs), long short-term memory (LSTM), and deep LSTM (DLSTM), DAerosol-NTM significantly improves prediction accuracy by 8–31% and precision by 46–91% and reduces the root mean square error (RMSE) by 24–85%. Additionally, DAerosol-NTM incorporates up to 20 years of particulate matter data in its external storage, making it the first model capable of predicting aerosol pollution surges. By analyzing the data from the previous 96 h, the optimal time interval before and after the aerosol event (TIBAAE) enables the prediction of aerosol events within the following 24 h. [ABSTRACT FROM AUTHOR]

The purpose of this article is to study the algorithmic complexity of the Besicovitch stability of noisy subshifts of finite type, a notion studied in a previous article [1]. First, we exhibit an unstable aperiodic tiling,and then see how it can serve as a building block to implement several reductions from classical undecidable problems on Turing machines. It will follow that the question of stability of subshifts of finite type is undecidable, and the strongest lower bound we obtain in the arithmetical hierarchy is Π 2 -hardness. Lastly, we prove that this decision problem,which requires to quantify over an uncountable set of probability measures,has a Π 4 upper bound. [ABSTRACT FROM AUTHOR]

For over two decades, Turing machines (TMs) have been studied as dynamical systems. Several results related to topological properties were established, such as equicontinuity, periodicity, mortality, and entropy. There are two main topological models for TMs, and these properties strongly depend on the considered model. Here, we focus on transitivity, minimality and other related properties. In the context of TMs, transitivity refers to the existence of a configuration whose evolution contains every possible pattern over any finite window. Minimality means that every configuration fulfills the aforementioned statement, which strongly restricts TM behaviour. This paper establishes relations between the following properties: transitivity, minimality, the existence of blocking words, aperiodicity and reversibility. It also explores some properties of the embedding technique, which combines two TMs to produce a third. This technique has been used in previous works to prove the undecidability of several dynamical properties. Here, we demonstrate its power and versatility and how the produced machine, under a few particular conditions, will inherit the properties of one of the original machines. [ABSTRACT FROM AUTHOR]

The thesis of the paper is that semiotic processes are intrinsic to computation and computational systems. An explanation of computation that does not take this semiotic dimension into account is incomplete. Semiosis is essential to computation and therefore requires a rigorous definition. To prove this thesis, the author analyzes two concepts of computation: the Turing machine and the mechanistic conception of physical computation. The paper is organized in two parts. The first part (Sects. 2 and 3) develops a re-interpretation of the Turing machine starting from Peirce's semiotics. The author shows how this reinterpretation allows overcoming the dualism between a purist and a realist version of the Turing machine. The second part of the paper (Sect. 4) shows how a mechanistic explanation of physical computation such as the one developed by Piccinini is incomplete without considering semiotic relations. The paper intends to be a contribution to the philosophical debate on computation. [ABSTRACT FROM AUTHOR]

Making grammars model makers as perceiving their environment and acting to transform it. Shape grammars, which model designers as manipulating shapes, are then a special case of making grammars where perceiving is limited to seeing and doing is limited to drawing. This paper develops set-theoretical and graph-theoretical formalizations of making grammars. Existing set-theoretical formalizations of shape grammars show that designing is visual computing by demonstrating that a shape grammar can be devised to simulate any Turing machine. However, there are no mathematical arguments showing how making grammars describe computation. Using a previously published example of a shape grammar and its corresponding making grammar, this paper combines ideas from ecological psychology with methods from set theory and graph theory to show that, for each Turing machine, a making grammar can be devised which simulates it. [ABSTRACT FROM AUTHOR]

Cell responses are usually viewed as transitive events with fixed inputs and outputs that are regulated by feedback loops. In contrast, directed cycles (DCs) have all nodes connected, and the flow is in a single direction. Consequently, DCs can regenerate themselves and implement intransitive logic. DCs are able to couple unrelated chemical reactions to each edge. The output depends upon which node is used as input. DCs can also undergo selection to minimize the loss of thermodynamic entropy while maximizing the gain of information entropy. The intransitive logic underlying DCs enhances their programmability and impacts their evolution. The natural selection of DCs favors the persistence, adaptability, and self-awareness of living organisms and does not depend solely on changes to coding sequences. Rather, the process can be RNA-directed. I use flipons, nucleic acid sequences that change conformation under physiological conditions, as a simple example and then describe more complex DCs. Flipons are often encoded by repeats and greatly increase the Kolmogorov complexity of genomes by adopting alternative structures. Other DCs allow cells to regenerate, recalibrate, reset, repair, and rewrite themselves, going far beyond the capabilities of current computational devices. Unlike Turing machines, cells are not designed to halt but rather to regenerate. [ABSTRACT FROM AUTHOR]

This article compares two methods of algorithmically processing bandlimited time-continuous signals in light of the general problem of finding "suitable" representations of analog information on digital hardware. Albeit abstract, we argue that this problem is fundamental in digital twinning, a signal-processing paradigm the upcoming 6G communication-technology standard relies on heavily. Using computable analysis, we formalize a general framework of machine-readable descriptions for representing analytic objects on Turing machines. Subsequently, we apply this framework to sampling and interpolation theory, providing a thoroughly formalized method for digitally processing the information carried by bandlimited analog signals. We investigate discrete-time descriptions, which form the implicit quasi-standard in digital signal processing, and establish continuous-time descriptions that take the signal's continuous-time behavior into account. Motivated by an exemplary application of digital twinning, we analyze a textbook model of digital communication systems accordingly. We show that technologically fundamental properties, such as a signal's (Banach-space) norm, can be computed from continuous-time, but not from discrete-time descriptions of the signal. Given the high trustworthiness requirements within 6G, e.g., employed software must satisfy assessment criteria in a provable manner, we conclude that the problem of "trustworthy" digital representations of analog information is indeed essential to near-future information technology. [ABSTRACT FROM AUTHOR]

An automaton is k-visit-bounded if during any computation its work tape head visits each tape cell at most k times. In this paper we consider stack automata which are k-visit-bounded for some integer k. This restriction resets the visits when popping (unlike similarly defined Turing machine restrictions) which we show allows the model to accept a proper superset of context-free languages and also a proper superset of languages of visit-bounded Turing machines. We study two variants of visit-bounded stack automata: one where only instructions that move the stack head downwards increase the number of visits of the destination cell, and another where any transition increases the number of visits. We prove that the two types of automata recognize the same languages. We then show that all languages recognized by visit-bounded stack automata are effectively semilinear, and hence are letter-equivalent to regular languages, which can be used to show other properties. [ABSTRACT FROM AUTHOR]

Semi-unification is the combination of first-order unification and first-order matching. The undecidability of semi-unification has been proven by Kfoury, Tiuryn, and Urzyczyn in the 1990s by Turing reduction from Turing machine immortality (existence of a diverging configuration). The particular Turing reduction is intricate, uses noncomputational principles, and involves various intermediate models of computation. The present work gives a constructive many-one reduction from the Turing machine halting problem to semi-unification. This establishes RE-completeness of semi-unification under many-one reductions. Computability of the reduction function, constructivity of the argument, and correctness of the argument is witnessed by an axiom-free mechanization in the Coq proof assistant. Arguably, this serves as comprehensive, precise, and surveyable evidence for the result at hand. The mechanization is incorporated into the existing, wellmaintained Coq library of undecidability proofs. Notably, a variant of Hooper's argument for the undecidability of Turing machine immortality is part of the mechanization. [ABSTRACT FROM AUTHOR]

In Freydenberger (Theory Comput Syst 53(2):159–193, 2013. https://doi.org/10.1007/s00224-012-9389-0), Freydenberger shows that the set of invalid computations of an extended Turing machine can be recognized by a synchronized regular expression [as defined in Della Penna et al. (Acta Informatica 39(1):31–70, 2003. https://doi.org/10.1007/s00236-002-0099-y)]. Therefore, the widely discussed predicate " = { 0 , 1 } ∗ " is not recursively enumerable for synchronized regular expressions (SRE). In this paper, we employ a stronger form of non-recursive enumerability called productiveness and show that the set of invalid computations of a deterministic Turing machine on a single input can be recognized by a synchronized regular expression. Hence, for a polynomial-time decidable subset of SRE, where each expression generates either { 0 , 1 } ∗ or { 0 , 1 } ∗ - { w } where w ∈ { 0 , 1 } ∗ , the predicate " = { 0 , 1 } ∗ " is productive. This result can be easily applied to other classes of language descriptors due to the simplicity of the construction in its proof. This result also implies that many computational problems, especially promise problems, for SRE are productive. These problems include language class comparison problems (e.g., does a given synchronized regular expression generate a context-free language?), and equivalence and containment problems of several types (e.g., does a given synchronized regular expression generate a language equal to a fixed unbounded regular set?). In addition, we study the descriptional complexity of SRE. A generalized method for studying trade-offs between SRE and many classes of language descriptors is established. [ABSTRACT FROM AUTHOR]

The identification of the mechanisms by which T-cell receptors (TCRs) interact with human antigens provides a crucial opportunity to develop new vaccines, diagnostics and immunotherapies. However, the accurate prediction and recognition of TCR–antigen pairing represents a substantial computational challenge in immunology. Existing tools only learn the binding patterns of antigens from many known TCR binding repertoires and fail to recognize antigens that have never been presented to the immune system or for which only a few TCR binding repertoires are known. However, the binding specificity for neoantigens or exogenous peptides is crucial for immune studies and immunotherapy. Therefore, we developed Pan-Peptide Meta Learning (PanPep), a general and robust framework to recognize TCR–antigen binding, by combining the concepts of meta-learning and the neural Turing machine. The neural Turing machine adds external memory to avoid forgetting previously learned tasks, which is used here to accurately predict TCR binding specificity with any peptide, particularly unseen ones. We applied PanPep to various challenging clinical tasks, including (1) qualitatively measuring the clonal expansion of T cells; (2) efficiently sorting responsive T cells in tumour neoantigen therapy; and (3) accurately identifying immune-responsive TCRs in a large cohort from a COVID-19 study. Our comprehensive tests show that PanPep outperforms existing tools. PanPep also offers interpretability, revealing the nature of peptide and TCR interactions in 3D crystal structures. We believe PanPep can be a useful tool to decipher TCR–antigen interactions and that it has broad clinical applications. Machine learning methods can predict and recognize binding patterns between T-cell receptors and human antigens, but they struggle with antigens for which no or little data exist regarding interactions with the immune system. A new method called PanPep based on meta-learning can learn quickly on new binding prediction tasks and accurately predicts pairing between T-cell receptors and new antigens. [ABSTRACT FROM AUTHOR]

Approaching limitations of digital computing technologies have spurred research in neuromorphic and other unconventional approaches to computing. Here we argue that if we want to engineer unconventional computing systems in a systematic way, we need guidance from a formal theory that is different from the classical symbolic-algorithmic Turing machine theory. We propose a general strategy for developing such a theory, and within that general view, a specific approach that we call fluent computing. In contrast to Turing, who modeled computing processes from a top-down perspective as symbolic reasoning, we adopt the scientific paradigm of physics and model physical computing systems bottom-up by formalizing what can ultimately be measured in a physical computing system. This leads to an understanding of computing as the structuring of processes, while classical models of computing systems describe the processing of structures. Learning from human brains to build powerful computers is attractive, yet extremely challenging due to the lack of a guiding computing theory. Jaeger et al. give a perspective on a bottom-up approach to engineer unconventional computing systems, which is fundamentally different to the classical theory based on Turing machines. [ABSTRACT FROM AUTHOR]

We have introduced and extended the notion of swarm automaton to analyze the computability using swarm movement represented by multiset rewriting. The two transitions, parallel and sequential, are considered to transform a configuration of multisets at each step in the swarm automaton. In this paper, we focus on the number of agents composing each configuration and analyze the computing power of swarm automaton. From the result of swarm automaton without position information, no swarm automaton has a universal computing power even though we can use infinitely many agents both in parallel rewriting and in sequential rewriting. On the other hand, when we add the information of position for each agent, the swarm automaton has universal computability. We need just four agents in a configuration to simulate any Turing machine. [ABSTRACT FROM AUTHOR]

We approach the question 'What is consciousness?' in a new way, not as Descartes' 'systematic doubt', but as how organisms find their way in their world. Finding one's way involves finding possible uses of features of the world that might be beneficial or avoiding those that might be harmful. 'Possible uses of X to accomplish Y' are 'affordances'. The number of uses of X is indefinite (or unknown), the different uses are unordered, are not listable, and are not deducible from one another. All biological adaptations are either affordances seized by heritable variation and selection or, far faster, by the organism acting in its world finding uses of X to accomplish Y. Based on this, we reach rather astonishing conclusions: 1. Artificial general intelligence based on universal Turing machines (UTMs) is not possible, since UTMs cannot 'find' novel affordances. 2. Brain-mind is not purely classical physics for no classical physics system can be an analogue computer whose dynamical behaviour can be isomorphic to 'possible uses'. 3. Brain-mind must be partly quantum—supported by increasing evidence at 6.0 to 7.3 sigma. 4. Based on Heisenberg's interpretation of the quantum state as 'potentia' converted to 'actuals' by measurement, where this interpretation is not a substance dualism, a natural hypothesis is that mind actualizes potentia. This is supported at 5.2 sigma. Then mind's actualizations of entangled brain-mind-world states are experienced as qualia and allow 'seeing' or 'perceiving' of uses of X to accomplish Y. We can and do jury-rig. Computers cannot. 5. Beyond familiar quantum computers, we discuss the potentialities of trans-Turing systems. [ABSTRACT FROM AUTHOR]

In this paper, we demonstrate a molecular system for the first active self-assembly linear DNA polymer that exhibits programmable molecular exponential growth in real time, also the first to implement "internal" parallel insertion that does not rely on adding successive layers to "external" edges for growth. Approaches like this can produce enhanced exponential growth behavior that is less limited by volume and external surface interference, for an early step toward efficiently building two and three dimensional shapes in logarithmic time. We experimentally demonstrate the division of these polymers via the addition of a single DNA complex that competes with the insertion mechanism and results in the exponential growth of a population of polymers per unit time. In the supplementary material, we note that an "extension" beyond conventional Turing machine theory is needed to theoretically analyze exponential growth itself in programmable physical systems. Sequential physical Turing Machines that run a roughly constant number of Turing steps per unit time cannot achieve an exponential growth of structure per time. In contrast, the "active" self-assembly model in this paper, computationally equivalent to a Push-Down Automaton, is exponentially fast when implemented in molecules, but is taxonomically less powerful than a Turing machine. In this sense, a physical Push-Down Automaton can be more powerful than a sequential physical Turing Machine, even though the Turing Machine can compute any computable function. A need for an "extended" computational/physical theory arises, described in the supplementary material section S1. [ABSTRACT FROM AUTHOR]

Evolution-communication spiking neural P systems with energy request rules (ECSNP-ER systems) are proposed and developed as a new variant of evolution-communication spiking neural P systems. In ECSNP-ER systems, in addition to spike-evolution rules and spike-communication rules, neurons also have energy request rules. Energy request rules are used to obtain energy from the environment needed for spike evolution and communication in neurons. The definition, structure and operations of ECSNP-ER systems are presented in detail. ECSNP-ER systems are proved to have the same computing capabilities as Turing machines by using them as number generating/accepting devices and function computing devices. Working non-deterministically, ECSNP-ER systems are used to solve NP-complete problems, using the SAT problem as an example, in linear time. [ABSTRACT FROM AUTHOR]

Biomolecular communication demands that interactions between parts of a molecular system act as scaffolds for message transmission. It also requires an organized system of signs—a communicative agency—for creating and transmitting meaning. The emergence of agency, the capacity to act in a given context and generate end‐directed behaviors, has baffled evolutionary biologists for centuries. Here, I explore its emergence with knowledge grounded in over two decades of evolutionary genomic and bioinformatic exploration. Biphasic processes of growth and diversification exist that generate hierarchy and modularity in biological systems at widely ranging time scales. Similarly, a biphasic process exists in communication that constructs a message before it can be transmitted for interpretation. Transmission dissipates matter‐energy and information and involves computation. Agency emerges when molecular machinery generates hierarchical layers of vocabularies in an entangled communication network clustered around the universal Turing machine of the ribosome. Computations canalize biological systems to perform biological functions in a dissipative quest to structure long‐lived occurrents. This occurs within the confines of a "triangle of persistence" that maximizes invariance with trade‐offs between economy, flexibility, and robustness. Thus, learning from previous historical and circumstantial experiences unifies modules in a hierarchy that expands the agency of systems. [ABSTRACT FROM AUTHOR]

The foundation of modern cryptography developed in 1976 considered security by modeling adversaries as polynomial-time Turing machines. However, recent advances in developing a general-purpose quantum computer have made a significant impact on modern cryptography because it overturns the security model. NTT's research on cryptography aims to provide technologies to ensure the security of modern information systems and create applications when quantum computers become widespread. This article reviews the 40 years of cryptologic research at NTT and outlines our current efforts. [ABSTRACT FROM AUTHOR]

Copyright of Artnodes is the property of Universitat Oberta de Catalunya and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)