China
Africa
Explore chapters and articles related to this topic
Introduction
Published in John N. Mordeson, Davender S. Malik, Fuzzy Automata and Languages, 2002
John N. Mordeson, Davender S. Malik
Definition 5.2.3 A linear bounded automaton is the same as a Turing automaton, but its input tape is finite. The length of the input tape of a linear bounded automaton is a linear function of the length of the input word printed on the tape.
Coding-theorem like behaviour and emergence of the universal distribution from resource-bounded algorithmic probability
Published in International Journal of Parallel, Emergent and Distributed Systems, 2019
Hector Zenil, Liliana Badillo, Santiago Hernández-Orozco, Francisco Hernández-Quiroz
The Chomsky hierarchy is a strict containment hierarchy of classes of formal grammars equivalent to different computational models of increasing computing power. At each of the 4 levels, grammars and automata compute a larger set of possible languages and strings. The four levels, from weaker to stronger computational power, are:The most restricted grammars generating the regular languages. They consist of rules with single non-terminal symbols on the left-hand side and strings of terminal symbols followed by at most one non-terminal symbol on the right-hand side. These types of rule are referred to as right linear (but a symmetrical left linear definition works as well). This level is studied by way of finite-state transducers (FST), a generalisation of finite-state automata (FSA) that produce an output at every step, generating a relation between input strings and output strings. Though apparently more general, FST-recognised languages are the same as FSA-accepted sets. Hence both can represent this level. We use an enumeration of transducers introduced in [24] where they also proved an invariance theorem [1,2,28], thus demonstrating that the enumeration choice is invariant (up to a constant).Grammars that generate the context-free languages. These kinds of grammars are extensively used in linguistics. The languages generated by CFG grammars are exactly the languages that can be recognized by a non-deterministic pushdown automaton. We denote this level by CFG. We generated production rules for 40,000 grammars according to a sound scheme introduced in [25].Grammars that generate the context-sensitive languages. The languages described by these grammars are all languages that can be recognized by a linear-bounded automaton (LBA), a Turing machine whose tape’s length is bounded by a constant times the length of the input. An AP-based variation is introduced here, and we denote it by LBA/AP.The least restricted grammar. Generates the languages that can be recognized by Turing machines, also called recursively enumerable languages. This is the level at which Turing-universality is achieved or required. We used previously generated distributions produced and reported in [26,27]We also explore the consequences of relaxing the halting configuration (e.g. halting state) in models of universal computation (Type-0) when it comes to comparing their output distributions.