- Fields of mathematics
- >
- Applied mathematics
- >
- Theoretical computer science
- >
- Theory of computation

Limits of computation

The limits of computation are governed by a number of different factors. In particular, there are several physical and practical limits to the amount of computation or data storage that can be perform

Bremermann's limit

Bremermann's limit, named after Hans-Joachim Bremermann, is a limit on the maximum rate of computation that can be achieved in a self-contained system in the material universe. It is derived from Eins

Busy beaver

In theoretical computer science, the busy beaver game aims at finding a terminating program of a given size that produces the most output possible. Since an endlessly looping program producing infinit

Semiotic engineering

Semiotic Engineering was originally proposed by Clarisse De Souza as a semiotic approach to designing user interface languages. Over the years, with research done at the Department of Informatics of t

X-machine

The X-machine (XM) is a theoretical model of computation introduced by Samuel Eilenberg in 1974.The X in "X-machine" represents the fundamental data type on which the machine operates; for example, a

List of undecidable problems

In computability theory, an undecidable problem is a type of computational problem that requires a yes/no answer, but where there cannot possibly be any computer program that always gives the correct

Gödel numbering

In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. The concept was dev

Typed lambda calculus

A typed lambda calculus is a typed formalism that uses the lambda-symbol to denote anonymous function abstraction. In this context, types are usually objects of a syntactic nature that are assigned to

Primitive recursive set function

In mathematics, primitive recursive set functions or primitive recursive ordinal functions are analogs of primitive recursive functions, defined for sets or ordinals rather than natural numbers. They

Intersection type discipline

In mathematical logic, the intersection type discipline is a branch of type theory encompassing type systems that use the intersection type constructor to assign multiple types to a single term.In par

Parallel terraced scan

The parallel terraced scan is a multi-agent based search technique that is basic to cognitive architectures, such as Copycat, Letter-string, the Examiner, Tabletop, and others. It was developed by and

Cylindric numbering

In computability theory a cylindric numbering is a special kind of numbering first introduced by Yuri L. Ershov in 1973. If a numbering is reducible to then there exists a computable function with . U

Brooks–Iyengar algorithm

The Brooks–Iyengar algorithm or Brooks–Iyengar hybrid algorithm is a distributed algorithm that improves both the precision and accuracy of the interval measurements taken by a distributed sensor netw

Byzantine fault

A Byzantine fault (also Byzantine generals problem, interactive consistency, source congruency, error avalanche, Byzantine agreement problem, and Byzantine failure) is a condition of a computer system

Turing machine equivalents

A Turing machine is a hypothetical computing device, first conceived by Alan Turing in 1936. Turing machines manipulate symbols on a potentially infinite strip of tape according to a finite table of r

International Conference on Reachability Problems

RP, the International Conference on Reachability Problems is an annual academic conference in thefield of computer science. The RP is specifically aimed at gathering together scholars from diverse dis

SXM (computational model)

No description available.

Nomogram

A nomogram (from Greek nomos νόμος, "law" and grammē γραμμή, "line"), also called a nomograph, alignment chart, or abac, is a graphical calculating device, a two-dimensional diagram designed to allow

Universality probability

Universality probability is an abstruse probability measure in computational complexity theory that concerns universal Turing machines.

Two Generals' Problem

In computing, the Two Generals' Problem is a thought experiment meant to illustrate the pitfalls and design challenges of attempting to coordinate an action by communicating over an unreliable link. I

Algorithmic game theory

Algorithmic game theory (AGT) is an area in the intersection of game theory and computer science, with the objective of understanding and design of algorithms in strategic environments. Typically, in

Self-reference

Self-reference occurs in natural or formal languages when a sentence, idea or formula refers to itself. The reference may be expressed either directly—through some intermediate sentence or formula—or

Size-change termination principle

The size-change termination principle (SCT) guarantees termination for a computer program by proving that infinite computations always trigger infinite descent in data values that are well-founded. Si

Semi-Thue system

In theoretical computer science and mathematical logic a string rewriting system (SRS), historically called a semi-Thue system, is a rewriting system over strings from a (usually finite) alphabet. Giv

Cylindrification

In computability theory a cylindrification is a construction that associates a cylindric numbering to each numbering. The concept was first introduced by Yuri L. Ershov in 1973.

Turing completeness

In computability theory, a system of data-manipulation rules (such as a computer's instruction set, a programming language, or a cellular automaton) is said to be Turing-complete or computationally un

Yao's test

In cryptography and the theory of computation, Yao's test is a test defined by Andrew Chi-Chih Yao in 1982, against pseudo-random sequences. A sequence of words passes Yao's test if an attacker with r

Computation history

In computer science, a computation history is a sequence of steps taken by an abstract machine in the process of computing its result. Computation histories are frequently used in proofs about the cap

Circuit (computer science)

In theoretical computer science, a circuit is a model of computation in which input values proceed through a sequence of gates, each of which computes a function. Circuits of this kind provide a gener

Entscheidungsproblem

In mathematics and computer science, the Entscheidungsproblem (pronounced [ɛntˈʃaɪ̯dʊŋspʁoˌbleːm], German for 'decision problem') is a challenge posed by David Hilbert and Wilhelm Ackermann in 1928. T

Sudan function

In the theory of computation, the Sudan function is an example of a function that is recursive, but not primitive recursive. This is also true of the better-known Ackermann function. The Sudan functio

Communicating X-Machine

The Communicating (Stream) X-Machine is a model of computation introduced by various researchers in the 1990s to model systems composed of communicating agents. The model exists in several variants, w

Computation in the limit

In computability theory, a function is called limit computable if it is the limit of a uniformly computable sequence of functions. The terms computable in the limit, limit recursive and recursively ap

Church–Turing thesis

In computability theory, the Church–Turing thesis (also known as computability thesis, the Turing–Church thesis, the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis

Computable set

In computability theory, a set of natural numbers is called computable, recursive, or decidable if there is an algorithm which takes a number as input, terminates after a finite amount of time (possib

Tail recursion

No description available.

Reachability problem

Reachability is a fundamental problem that appears in several different contexts: finite- and infinite-state concurrent systems, computational models like cellular automata and Petri nets, program ana

Admissible numbering

In computability theory, admissible numberings are enumerations (numberings) of the set of partial computable functions that can be converted to and from the standard numbering. These numberings are a

Wang tile

Wang tiles (or Wang dominoes), first proposed by mathematician, logician, and philosopher Hao Wang in 1961, are a class of formal systems. They are modelled visually by square tiles with a color on ea

Extended finite-state machine

In a conventional finite state machine, the transition is associated with a set of input Boolean conditions and a set of output Boolean functions. In an extended finite state machine (EFSM) model, the

Simply typed lambda calculus

The simply typed lambda calculus, a formof type theory, is a typed interpretation of the lambda calculus with only one type constructor that builds function types. It is the canonical and simplest exa

Markov algorithm

In theoretical computer science, a Markov algorithm is a string rewriting system that uses grammar-like rules to operate on strings of symbols. Markov algorithms have been shown to be Turing-complete,

Computability

Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer s

Mortality (computability theory)

In computability theory, the mortality problem is a decision problem which can be stated as follows: Given a Turing machine, decide whether it halts when run on any configuration (not necessarily a st

Ackermann function

In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive.

Omega language

In formal language theory within theoretical computer science, an infinite word is an infinite-length sequence (specifically, an ω-length sequence) of symbols, and an ω-language is a set of infinite w

Mutual recursion

In mathematics and computer science, mutual recursion is a form of recursion where two mathematical or computational objects, such as functions or datatypes, are defined in terms of each other. Mutual

Blockhead (thought experiment)

Blockhead is the name of a theoretical computer system invented as part of a thought experiment by philosopher Ned Block, which appeared in a paper titled "Psychologism and Behaviorism". Block did not

Super-recursive algorithm

In computability theory, super-recursive algorithms are a generalization of ordinary algorithms that are more powerful, that is, compute more than Turing machines. The term was introduced by Mark Burg

Undefined value

In computing (particularly, in programming), undefined value is a condition where an expression does not have a correct value, although it is syntactically correct. An undefined value must not be conf

Computable function

Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is com

Rounding

Rounding means replacing a number with an approximate value that has a shorter, simpler, or more explicit representation. For example, replacing $23.4476 with $23.45, the fraction 312/937 with 1/3, or

Quantum Byzantine agreement

Byzantine fault tolerant protocols are algorithms that are robust to arbitrary types of failures in distributed algorithms. The Byzantine agreement protocol is an essential part of this task. The cons

Stream X-Machine

The Stream X-machine (SXM) is a model of computation introduced by Gilbert Laycock in his 1993 PhD thesis, The Theory and Practice of Specification Based Software Testing.Based on Samuel Eilenberg's X

General recursive function

In mathematical logic and computer science, a general recursive function, partial recursive function, or μ-recursive function is a partial function from natural numbers to natural numbers that is "com

Turing tarpit

A Turing tarpit (or Turing tar-pit) is any programming language or computer interface that allows for flexibility in function but is difficult to learn and use because it offers little or no support f

Theory of computation

In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they

Hypercomputation

Hypercomputation or super-Turing computation refers to models of computation that can provide outputs that are not Turing-computable. Super-Turing computing, introduced at the early 1990's by Hava Sie

Reachability analysis

Reachability analysis is a solution to the reachability problem in the particular context of distributed systems. It is used to determine which global states can be reached by a distributed system whi

Turing's proof

Turing's proof is a proof by Alan Turing, first published in January 1937 with the title "On Computable Numbers, with an Application to the Entscheidungsproblem". It was the second proof (after Church

Ten15

Ten15 is an algebraically specified abstract machine. It was developed by Foster, Currie et al. at the Royal Signals and Radar Establishment at Malvern, Worcestershire, during the 1980s. It arose from

Chain rule for Kolmogorov complexity

The chain rule for Kolmogorov complexity is an analogue of the chain rule for information entropy, which states: That is, the combined randomness of two sequences X and Y is the sum of the randomness

Computational semiotics

Computational semiotics is an interdisciplinary field that applies, conducts, and draws on research in logic, mathematics, the theory and practice of computation, formal and natural language studies,

Recursively enumerable language

In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable, Turing-acceptable or Turing-recognizable) if it i

List of computability and complexity topics

This is a list of computability and complexity topics, by Wikipedia page. Computability theory is the part of the theory of computation that deals with what can be computed, in principle. Computationa

Scale factor (computer science)

In computer science, a scale factor is a number used as a multiplier to represent a number on a different scale, functioning similarly to an exponent in mathematics. A scale factor is used when a real

First Draft of a Report on the EDVAC

The First Draft of a Report on the EDVAC (commonly shortened to First Draft) is an incomplete 101-page document written by John von Neumann and distributed on June 30, 1945 by Herman Goldstine, securi

Enumerator (computer science)

An enumerator is a Turing machine with an attached printer. The Turing machine can use that printer as an output device to print strings. Every time the Turing machine wants to add a string to the lis

Primitive recursive function

In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number

Parallel computation thesis

In computational complexity theory, the parallel computation thesis is a hypothesis which states that the time used by a (reasonable) parallel machine is polynomially related to the space used by a se

History of the Church–Turing thesis

The history of the Church–Turing thesis ("thesis") involves the history of the development of the study of the nature of functions whose values are effectively calculable; or, in more modern terms, fu

Chaitin's constant

In the computer science subfield of algorithmic information theory, a Chaitin constant (Chaitin omega number) or halting probability is a real number that, informally speaking, represents the probabil

Interactive computation

In computer science, interactive computation is a mathematical model for computation that involves input/output communication with the external world during computation.

Recursive language

In mathematics, logic and computer science, a formal language (a set of finite sequences of symbols taken from a fixed alphabet) is called recursive if it is a recursive subset of the set of all possi

Numbering (computability theory)

In computability theory a numbering is the assignment of natural numbers to a set of objects such as functions, rational numbers, graphs, or words in some formal language. A numbering can be used to t

Computably enumerable set

In computability theory, a set S of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable

Real computation

In computability theory, the theory of real computation deals with hypothetical computing machines using infinite-precision real numbers. They are given this name because they operate on the set of re

Church–Turing–Deutsch principle

In computer science and quantum physics, the Church–Turing–Deutsch principle (CTD principle) is a stronger, physical form of the Church–Turing thesis formulated by David Deutsch in 1985. The principle

Description number

Description numbers are numbers that arise in the theory of Turing machines. They are very similar to Gödel numbers, and are also occasionally called "Gödel numbers" in the literature. Given some univ

Digital physics

Digital physics is a speculative idea that the universe can be conceived of as a vast, digital computation device, or as the output of a deterministic or probabilistic computer program. The hypothesis

Nondeterministic algorithm

In computer programming, a nondeterministic algorithm is an algorithm that, even for the same input, can exhibit different behaviors on different runs, as opposed to a deterministic algorithm. There a

Transcomputational problem

In computational complexity theory, a transcomputational problem is a problem that requires processing of more than 1093 bits of information. Any number greater than 1093 is called a transcomputationa

X-Machine Testing

The (Stream) X-Machine Testing Methodology is a complete functional testing approach to software- and hardware testing that exploits the scalability of the Stream X-Machine model of computation. Using

Computable number

In mathematics, computable numbers are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm. They are also known as the recursive numbers, effective

Shadow square

The shadow square, also known as an altitude scale, was an instrument used to determine the linear height of an object, in conjunction with the alidade, for angular observations. An early example was

Halting problem

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to ru

Introduction to the Theory of Computation

Introduction to the Theory of Computation (ISBN 0-534-95097-3) is a textbook in theoretical computer science, written by Michael Sipser and first published by PWS Publishing in 1997.

Post correspondence problem

The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946. Because it is simpler than the halting problem and the Entscheidungsproblem it is often use

Effective method

In logic, mathematics and computer science, especially metalogic and computability theory, an effective method or effective procedure is a procedure for solving a problem by any intuitively 'effective

Tarski–Kuratowski algorithm

In computability theory and mathematical logic the Tarski–Kuratowski algorithm is a non-deterministic algorithm which produces an upper bound for the complexity of a given formula in the arithmetical

Turing degree

In computer science and mathematical logic the Turing degree (named after Alan Turing) or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set

Recursion

Recursion (adjective: recursive) occurs when a thing is defined in terms of itself or of its type. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common appl

© 2023 Useful Links.