|
Pointer Algorithm
In theoretical computer science a pointer machine is an "atomistic" ''abstract computational machine'' model akin to the random-access machine. A pointer algorithm is an algorithm restricted to the pointer machine model. Depending on the type, a pointer machine may be called a linking automaton, a KU-machine, an SMM, an atomistic LISP machine, a tree-pointer machine, etc. (cf Ben-Amram 1995). At least three major varieties exist in the literature—the Kolmogorov-Uspenskii model (KUM, KU-machine), the Knuth linking automaton, and the Schönhage Storage Modification Machine model (SMM). The SMM seems to be the most common. From its "read-only tape" (or equivalent) a pointer machine receives ''input''—bounded symbol-sequences ("words") made of at least two symbols e.g. -- and it writes ''output'' symbol-sequences on an output "write-only" tape (or equivalent). To transform a symbol-sequence (input word) to an output symbol-sequence the machine is equipped with a "program"—a fi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Theoretical Computer Science
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumscribe the theoretical areas precisely. The Association for Computing Machinery, ACM's ACM SIGACT, Special Interest Group on Algorithms and Computation Theory (SIGACT) provides the following description: History While logical inference and mathematical proof had existed previously, in 1931 Kurt Gödel proved with his incompleteness theorem that there are fundamental limitations on what statements could be proved or disproved. Information theory was added to the field with a 1948 mathematical theory of communication by Claude Shannon. In the same decade, Donald Hebb introduced a mathematical model of Hebbian learning, learning in the brain. With mounting biological data supporting this hypothesis with some modification, the fields of n ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Counter Machine
A counter machine is an abstract machine used in a formal logic and theoretical computer science to model computation. It is the most primitive of the four types of register machines. A counter machine comprises a set of one or more unbounded ''registers'', each of which can hold a single non-negative integer, and a list of (usually sequential) arithmetic and control instructions for the machine to follow. The counter machine is typically used in the process of designing parallel algorithms in relation to the mutual exclusion principle. When used in this manner, the counter machine is used to model the discrete time-steps of a computational system in relation to memory accesses. By modeling computations in relation to the memory accesses for each respective computational step, parallel algorithms may be designed in such a matter to avoid interlocking, the simultaneous writing operation by two (or more) threads to the same memory address. Basic features For a given counter machin ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Peter Van Emde Boas
Peter van Emde Boas (born 3 April 1945, Amsterdam) is a Dutch computer scientist and professor at the University of Amsterdam. He gained his doctorate in 1974 under Adriaan van Wijngaarden. The Van Emde Boas tree A van Emde Boas tree (), also known as a vEB tree or van Emde Boas priority queue, is a tree data structure which implements an associative array with -bit integer keys. It was invented by a team led by Dutch computer scientist Peter van Emde Boa ... is named after him.Peter van Emde Boas '' Preserving order in a forest in less than logarithmic time'', Proceedings of the 16th Annual Symposium on Foundations of Computer Science, 1975, S. 75-84 - doi:10.1109/SFCS.1975.26 References External links Homepage 1945 births Living people Dutch computer scientists Theoretical computer scientists University of Amsterdam faculty University of Amsterdam alumni Scientists from Amsterdam {{Netherlands-scientist-stub ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Arnold Schönhage
Arnold Schönhage (born 1 December 1934 in Lockhausen, now Bad Salzuflen) is a German mathematician and computer scientist. Schönhage was professor at the Rheinische Friedrich-Wilhelms-Universität, Bonn, and also in Tübingen and Konstanz. He now lives near Bonn. Together with Volker Strassen he developed the Schönhage–Strassen algorithm for fast integer multiplication that has a run-time of '' O''(''N'' log ''N'' log log ''N''). Schönhage designed and implemented together with Andreas F. W. Grotefeld and Ekkehart Vetter a multitape Turing machine, called TP, in software. The machine is programmed in TPAL, an assembler language In computer programming, assembly language (or assembler language, or symbolic machine code), often referred to simply as Assembly and commonly abbreviated as ASM or asm, is any low-level programming language with a very strong correspondence be .... They implemented numerous numerical algorithms including the Sch ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
John E
John is a common English name and surname: * John (given name) * John (surname) John may also refer to: New Testament Works * Gospel of John, a title often shortened to John * First Epistle of John, often shortened to 1 John * Second Epistle of John, often shortened to 2 John * Third Epistle of John, often shortened to 3 John People * John the Baptist (died c. AD 30), regarded as a prophet and the forerunner of Jesus Christ * John the Apostle (lived c. AD 30), one of the twelve apostles of Jesus * John the Evangelist, assigned author of the Fourth Gospel, once identified with the Apostle * John of Patmos, also known as John the Divine or John the Revelator, the author of the Book of Revelation, once identified with the Apostle * John the Presbyter, a figure either identified with or distinguished from the Apostle, the Evangelist and John of Patmos Other people with the given name Religious figures * John, father of Andrew the Apostle and Saint Peter * Pope J ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Yuri Gurevich
Yuri Gurevich, Professor Emeritus at the University of Michigan, is an American computer scientist and mathematician and the inventor of abstract state machines. Gurevich was born and educated in the Soviet Union. He taught mathematics there and then in Israel before moving to the United States in 1982. The best-known work of his Soviet period is on the ''classical decision problem''. In Israel, Gurevich worked with Saharon Shelah on monadic second-order theories. The ''Forgetful Determinacy Theorem'' of Gurevich– Harrington is of that period as well. From 1982 to 1998, Gurevich taught computer science at the University of Michigan, where he started to work on various aspects of computational complexity theory including average case complexity. He became one of the founders of the emerging field of finite model theory. Most importantly, he became interested in the problem of what an algorithm is. This led him to the theory of abstract state machines (ASMs). The ASM Thesis s ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Vladimir Andreyevich Uspensky
Vladimir Andreyevich Uspensky (Russian: Влади́мир Андре́евич Успе́нский; 27 November 1930 – 27 June 2018) was a Russian mathematician, linguist, writer, doctor of physics and mathematics (1964). He was the author of numerous papers on mathematical logic and linguistics. In addition, he also penned a number of memoir essays. Uspensky initiated a reform of linguistic education in Russia. Biography Uspensky graduated in 1952 from the MSU Faculty of Mechanics and Mathematics (Lomonosov Moscow State University). He was a student of Andrey Kolmogorov. He was the head of the Chair of Mathematical Logic and Theory of Algorithms in the MSU Faculty of Mechanics and Mathematics (1995) and one of the founders of the Structural Linguistics branch (now the Theoretical and Applied Linguistics branch) in the MSU Faculty of Philology, where he also taught. He was the author of many books and of over 100 research papers. He prepared 25 candidate A candidate, or ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Andrey Kolmogorov
Andrey Nikolaevich Kolmogorov ( rus, Андре́й Никола́евич Колмого́ров, p=ɐnˈdrʲej nʲɪkɐˈlajɪvʲɪtɕ kəlmɐˈɡorəf, a=Ru-Andrey Nikolaevich Kolmogorov.ogg, 25 April 1903 – 20 October 1987) was a Soviet mathematician who contributed to the mathematics of probability theory, topology, intuitionistic logic, turbulence, classical mechanics, algorithmic information theory and computational complexity. Biography Early life Andrey Kolmogorov was born in Tambov, about 500 kilometers south-southeast of Moscow, in 1903. His unmarried mother, Maria Y. Kolmogorova, died giving birth to him. Andrey was raised by two of his aunts in Tunoshna (near Yaroslavl) at the estate of his grandfather, a well-to-do nobleman. Little is known about Andrey's father. He was supposedly named Nikolai Matveevich Kataev and had been an agronomist. Kataev had been exiled from St. Petersburg to the Yaroslavl province after his participation in the revolutionary movem ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Amir Ben-Amram
Emir (; ar, أمير ' ), sometimes transliterated amir, amier, or ameer, is a word of Arabic origin that can refer to a male monarch, aristocrat, holder of high-ranking military or political office, or other person possessing actual or ceremonial authority. The title has a long history of use in the Arab World, East Africa, West Africa, Central Asia, and the Indian subcontinent. In the modern era, when used as a formal monarchical title, it is roughly synonymous with "prince", applicable both to a son of a hereditary monarch, and to a reigning monarch of a sovereign principality, namely an emirate. The feminine form is emira ( '), a cognate for "princess". Prior to its use as a monarchical title, the term "emir" was historically used to denote a "commander", "general", or "leader" (for example, Amir al-Mu'min). In contemporary usage, "emir" is also sometimes used as either an honorary or formal title for the head of an Islamic, or Arab (regardless of religion) organisatio ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Post–Turing Machine
A Post–Turing machineRajendra Kumar, ''Theory of Automata'', Tata McGraw-Hill Education, 2010, p. 343. is a "program formulation" of a type of Turing machine, comprising a variant of Emil Post's Turing-equivalent model of computation. Post's model and Turing's model, though very similar to one another, were developed independently. Turing's paper was received for publication in May 1936, followed by Post's in October. A Post–Turing machine uses a binary alphabet, an infinite sequence of binary storage locations, and a primitive programming language with instructions for bi-directional movement among the storage locations and alteration of their contents one at a time. The names "Post–Turing program" and "Post–Turing machine" were used by Martin Davis in 1973–1974 (Davis 1973, p. 69ff). Later in 1980, Davis used the name "Turing–Post program" (Davis, in Steen p. 241). 1936: Post model In his 1936 paper "Finite Combinatory Processes—Formulation 1", ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Von Neumann Architecture
The von Neumann architecture — also known as the von Neumann model or Princeton architecture — is a computer architecture based on a 1945 description by John von Neumann, and by others, in the ''First Draft of a Report on the EDVAC''. The document describes a design architecture for an electronic digital computer with these components: * A processing unit with both an arithmetic logic unit and processor registers * A control unit that includes an instruction register and a program counter * Memory that stores data and instructions * External mass storage * Input and output mechanisms.. The term "von Neumann architecture" has evolved to refer to any stored-program computer in which an instruction fetch and a data operation cannot occur at the same time (since they share a common bus). This is referred to as the von Neumann bottleneck, which often limits the performance of the corresponding system. The design of a von Neumann architecture machine is simpler than in a Harva ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Universal Turing Machine
In computer science, a universal Turing machine (UTM) is a Turing machine that can simulate an arbitrary Turing machine on arbitrary input. The universal machine essentially achieves this by reading both the description of the machine to be simulated as well as the input to that machine from its own tape. Alan Turing introduced the idea of such a machine in 1936–1937. This principle is considered to be the origin of the idea of a stored-program computer used by John von Neumann in 1946 for the "Electronic Computing Instrument" that now bears von Neumann's name: the von Neumann architecture. Martin Davis, ''The universal computer : the road from Leibniz to Turing'' (2017) In terms of computational complexity, a multi-tape universal Turing machine need only be slower by logarithmic factor compared to the machines it simulates. Introduction Every Turing machine computes a certain fixed partial computable function from the input strings over its alphabet. In that sense it be ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
.jpg "Click for more on -> Amir Ben-Amram")
