Crossing sequence (Turing machines)
- Crossing sequence (Turing machines)
-
In theoretical computer science, a crossing sequence at boundary k is the sequence of the states of a Turing machine in which it is at the moments when its head crosses the boundary between cells k and k+1 on the tape, i.e., when the head is over cell k and its next position is to be over cell k+1. The crossing sequence for an input I and boundary k is denoted Sk(I).
Study of crossing sequences is carried out, e.g., in computational complexity theory.
References
Wikimedia Foundation.
2010.
Look at other dictionaries:
Crossing sequence — may refer to: Crossing sequence (signal), a sound pattern when a train crosses a level crossing Crossing sequence (operation), a sequence of safety actions carried out when a train approeches and passes a level crossing Crossing sequence (Turing… … Wikipedia
List of mathematics articles (A) — NOTOC A A Beautiful Mind A Beautiful Mind (book) A Beautiful Mind (film) A Brief History of Time (film) A Course of Pure Mathematics A curious identity involving binomial coefficients A derivation of the discrete Fourier transform A equivalence A … Wikipedia
Structured programming — can be seen as a subset or subdiscipline of procedural programming, one of the major programming paradigms. It is most famous for removing or reducing reliance on the GOTO statement.Historically, several different structuring techniques or… … Wikipedia
X-machine — The X machine ( XM ) is a theoretical model of computation introduced by Samuel Eilenberg in 1974.S. Eilenberg (1974) Automata, Languages and Machines, Vol. A . Academic Press, London.] The X in X machine represents the fundamental data type on… … Wikipedia
computer science — computer scientist. the science that deals with the theory and methods of processing information in digital computers, the design of computer hardware and software, and the applications of computers. [1970 75] * * * Study of computers, their… … Universalium
literature — /lit euhr euh cheuhr, choor , li treuh /, n. 1. writings in which expression and form, in connection with ideas of permanent and universal interest, are characteristic or essential features, as poetry, novels, history, biography, and essays. 2.… … Universalium
Marian Rejewski — (probably 1932, the year he first solved the Enigma machine). Courtesy of Janina Sylwestrzak, Rejewski s daughter. Born Marian Adam Rejewski August 16, 1905(1905 0 … Wikipedia
Model of Hierarchical Complexity — The model of hierarchical complexity is a framework for scoring how complex a behavior is. It quantifies the order of hierarchical complexity of a task based on mathematical principles of how the information is organized and of information… … Wikipedia
