Find link

Computability not in Random-access stored-program machine

language:

Find link is a tool written by Edward Betts.

Longer titles found: Computability in Analysis and Physics (view), Computability in Europe (view), Computability logic (view), Computability theory (view), List of computability and complexity topics (view), Numbering (computability theory) (view), Logics for computability (view), Index set (computability) (view), Reduction (computability theory) (view), Low (computability) (view), Forcing (computability) (view), Basis theorem (computability) (view), Mortality (computability theory) (view)

searching for Computability 128 found (917 total)

alternate case: computability

ACM SIGACT (398 words) [view diff] no match in snippet view article find links to article

ACM SIGACT or SIGACT is the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, whose purpose is support of

True arithmetic (1,133 words) [view diff] exact match in snippet view article find links to article

184 Boolos, George; Burgess, John P.; Jeffrey, Richard C. (2002), Computability and logic (4th ed.), Cambridge University Press, ISBN 978-0-521-00758-0

ALL (complexity) (57 words) [view diff] exact match in snippet view article

In computability and complexity theory, ALL is the class of all decision problems. ALL contains all of the complex classes of decision problems, including

Zeno machine (877 words) [view diff] no match in snippet view article find links to article

In mathematics and computer science, Zeno machines (abbreviated ZM, and also called accelerated Turing machine, ATM) are a hypothetical computational model

List of types of numbers (1,188 words) [view diff] no match in snippet view article find links to article

Numbers can be classified according to how they are represented or according to the properties that they have. Natural numbers ( N {\displaystyle \mathbb

Classification of manifolds (2,310 words) [view diff] no match in snippet view article find links to article

In mathematics, specifically geometry and topology, the classification of manifolds is a basic question, about which much is known, and many open questions

To Mock a Mockingbird (383 words) [view diff] exact match in snippet view article find links to article

expressive power of set theory, and with deep connections to questions of computability and provability. Smullyan's exposition takes the form of an imaginary

Robert I. Soare (171 words) [view diff] exact match in snippet view article find links to article

has done other work in mathematical logic, primarily in the area of computability theory. His doctoral students at the University of Chicago have included

BlooP and FlooP (696 words) [view diff] exact match in snippet view article find links to article

as models of computation, and have sometimes been used in teaching computability. The only variables are OUTPUT (the return value of the procedure) and

The Annotated Turing (276 words) [view diff] exact match in snippet view article find links to article

Annotated Turing: A Guided Tour Through Alan Turing’s Historic Paper on Computability and the Turing Machine is a book by Charles Petzold, published in 2008

Nir Shavit (386 words) [view diff] exact match in snippet view article find links to article

work on applying tools from algebraic topology to model shared memory computability, and a winner of the 2012 Dijkstra Prize for the introduction and first

Dimiter Skordev (226 words) [view diff] exact match in snippet view article find links to article

research in Bulgaria who developed a Bulgarian school in the theory of computability, namely the algebraic (or axiomatic) recursion theory. He was the 1981

Semicomputable function (272 words) [view diff] exact match in snippet view article find links to article

In computability theory, a semicomputable function is a partial function f : Q → R {\displaystyle f:\mathbb {Q} \rightarrow \mathbb {R} } that can be

Rado's theorem (Ramsey theory) (606 words) [view diff] no match in snippet view article

Rado's theorem is a theorem from the branch of mathematics known as Ramsey theory. It is named for the German mathematician Richard Rado. It was proved

Approximation error (2,701 words) [view diff] exact match in snippet view article find links to article

absolute error ε, demonstrating that polynomial computability with relative error implies polynomial computability with absolute error.: 34 The reverse implication

Limit (mathematics) (6,042 words) [view diff] no match in snippet view article

In mathematics, a limit is the value that a function (or sequence) approaches as the argument (or index) approaches some value. Limits of functions are

Black swan theory (2,648 words) [view diff] exact match in snippet view article find links to article

expectations in history, science, finance, and technology. The non-computability of the probability of consequential rare events using scientific methods

Random-access stored-program machine (2,620 words) [view diff] exact match in snippet view article find links to article

Register machine. George Boolos, John P. Burgess, Richard Jeffrey (2002), Computability and Logic: Fourth Edition, Cambridge University Press, Cambridge, England

Counter machine (4,660 words) [view diff] exact match in snippet view article find links to article

Boolos, George; Burgess, John P.; Jeffrey, Richard (2007) [1974]. Computability and Logic (5th ed.). Cambridge, England: Cambridge University Press

Robert W. Floyd (1,171 words) [view diff] exact match in snippet view article find links to article

Beigel, of the textbook The Language of Machines: an Introduction to Computability and Formal Languages. Floyd supervised seven Ph.D. graduates. Floyd

[at Wikidata] (September 1961). "An Informal Arithmetical Approach to Computability and Computation". Canadian Mathematical Bulletin. 4 (3): 89, 279–293

Counter-machine model (3,298 words) [view diff] exact match in snippet view article find links to article

quickly as possible the computability of all partial recursive functions Péter's is perhaps the best; for proving their computability by Turing machines a

PR (complexity) (415 words) [view diff] exact match in snippet view article

2016). S. Barry Cooper (2004). Computability Theory. Chapman & Hall. ISBN 1-58488-237-9. Herbert Enderton (2011). Computability Theory. Academic Press.

Descriptive Complexity (612 words) [view diff] exact match in snippet view article find links to article

properties using different types of logic is shown to be equivalent to their computability in different types of resource-bounded models of computation. It was

Malament–Hogarth spacetime (1,005 words) [view diff] exact match in snippet view article find links to article

ISSN 0894-9875. Hogarth, Mark (1994). "Non-Turing Computers and Non-Turing Computability". PSA: Proceedings of the Biennial Meeting of the Philosophy of Science

Helmut Schwichtenberg (374 words) [view diff] exact match in snippet view article find links to article

Schwichtenberg deals with, among other things, proof theory, theory of computability, lambda calculus and applications of logic in computer science. He is

Finite-state machine (4,528 words) [view diff] exact match in snippet view article find links to article

Catalog Number 67-25924. Boolos, George; Jeffrey, Richard (1999) [1989]. Computability and Logic (3rd ed.). Cambridge, England: Cambridge University Press

List of things named after Alan Turing (331 words) [view diff] exact match in snippet view article find links to article

Turing (cipher) Turing College, Kent, England Turing completeness Turing computability Turing degree Turing Foundation, Amsterdam, Netherlands Turing Gateway

Pointer machine (1,556 words) [view diff] exact match in snippet view article find links to article

machine"?, SIGACT News (ACM Special Interest Group on Automata and Computability Theory)", volume 26, 1995. Wherein Ben-Amram describes the types and

Nataša Jonoska (385 words) [view diff] exact match in snippet view article find links to article

Science, the International Journal of Foundations of Computer Science, Computability, and Natural Computing. In 2022 she was awarded a Simons Fellowship

Random-access machine (7,515 words) [view diff] exact match in snippet view article find links to article

ISBN 0-07-004357-4}. George Boolos, John P. Burgess, Richard Jeffrey (2002), Computability and Logic: Fourth Edition, Cambridge University Press, Cambridge, England

Algorithmic probability (2,734 words) [view diff] exact match in snippet view article find links to article

to a universal Turing machine). The prior is universal in the Turing-computability sense, i.e. no string has zero probability. It is not computable, but

Post–Turing machine (2,767 words) [view diff] exact match in snippet view article find links to article

computation. Includes a little biography of Emil Post. Martin Davis, Computability: with Notes by Barry Jacobs, Courant Institute of Mathematical Sciences

Elementary cellular automaton (2,819 words) [view diff] exact match in snippet view article find links to article

In mathematics and computability theory, an elementary cellular automaton is a one-dimensional cellular automaton where there are two possible states

John Truss (1,358 words) [view diff] exact match in snippet view article find links to article

Symbolic Logic in Leeds in July 1997 on sets and proofs and models and computability. The volumes were welcomed by philosopher Graham Priest of the University

Carl Posy (221 words) [view diff] exact match in snippet view article find links to article

Mathematics: Modern Essays, Springer, 1992. ISBN 978-0-7923-1495-0 Computability: Turing, Gödel, Church, and Beyond (with Jack Copeland and Oron Shagrir)

Computable real function (334 words) [view diff] exact match in snippet view article find links to article

In mathematical logic, specifically computability theory, a function f : R → R {\displaystyle f\colon \mathbb {R} \to \mathbb {R} } is sequentially computable

László Kalmár (711 words) [view diff] exact match in snippet view article find links to article

York: Van Nostrand. OCLC 523942. Schwichtenberg, Helmut. "Computability". see under "Computability" Schwichtenberg, Helmut (2007). "Recursion Theory (Notes

Lyapunov time (269 words) [view diff] exact match in snippet view article find links to article

121.1171T. doi:10.1086/318732. Gerlach, E. (2009). "On the Numerical Computability of Asteroidal Lyapunov Times". arXiv:0901.4871 [physics.comp-ph].

Lyapunov time (269 words) [view diff] exact match in snippet view article find links to article

121.1171T. doi:10.1086/318732. Gerlach, E. (2009). "On the Numerical Computability of Asteroidal Lyapunov Times". arXiv:0901.4871 [physics.comp-ph].

Function problem (1,174 words) [view diff] exact match in snippet view article find links to article

x , y ) ∈ R {\displaystyle (x,y)\in R} . Therefore the question of computability of proofs is not separated from the question of their existence. To

Malware research (1,112 words) [view diff] exact match in snippet view article find links to article

program could reproduce itself. This constituted a plausibility result in computability theory. Fred Cohen experimented with computer viruses and confirmed

FP (complexity) (354 words) [view diff] exact match in snippet view article

Elaine (2008). "28.10 "The problem classes FP and FNP"". Automata, computability and complexity: theory and applications. Prentice Hall. pp. 689–694

Recursive function (94 words) [view diff] exact match in snippet view article find links to article

defines a sequence from initial values Recursion theory, the study of computability This disambiguation page lists articles associated with the title Recursive

John P. Burgess (251 words) [view diff] exact match in snippet view article find links to article

2005. Fixing Frege, Princeton University Press. ISBN 0691122318 2007. Computability and Logic (with George Boolos and Richard C. Jeffrey), Cambridge University

CE (645 words) [view diff] exact match in snippet view article find links to article

last number entered Computably enumerable, a property of some sets in computability theory, abbreviated c.e. Computer engineering, a branch of engineering

Richard Jeffrey (1,120 words) [view diff] exact match in snippet view article find links to article

Formal Logic: Its Scope and Limits, a basic introduction to logic, and Computability and Logic, a more advanced text dealing with, among other things, the

Resultant (8,057 words) [view diff] no match in snippet view article find links to article

In mathematics, the resultant of two polynomials is a polynomial expression of their coefficients that is equal to zero if and only if the polynomials

Zellig Harris (7,268 words) [view diff] exact match in snippet view article find links to article

1993b). Hoenigswald (1996). Sager, Naomi & Ngô, Thanh Nhàn (2002). "The computability of strings, transformations, and sublanguage". In Nevin, Bruce & Johnson

Wadge hierarchy (1,336 words) [view diff] exact match in snippet view article find links to article

lemma for Borel sets. Wadge's lemma is similar to the cone lemma from computability theory. The Wadge game is a simple infinite game used to investigate

Edgar H. Brown (388 words) [view diff] exact match in snippet view article find links to article

was George W. Whitehead, and his doctoral dissertation was on Finite Computability of the Homotopy Groups of Finite Groups. In 1962–63 he visited the Institute

Walter Carnielli (1,075 words) [view diff] exact match in snippet view article find links to article

and W. A. Carnielli. Computability: computable functions, logic and the foundations of mathematics, with the timeline Computability and Undecidability.

Edgar H. Brown (388 words) [view diff] exact match in snippet view article find links to article

was George W. Whitehead, and his doctoral dissertation was on Finite Computability of the Homotopy Groups of Finite Groups. In 1962–63 he visited the Institute

TT (584 words) [view diff] exact match in snippet view article find links to article

tt-reduction (truth-table reduction), a kind of transformation used in computability theory <tt>...</tt> (short for teletype), an HTML presentation element

Ramsey theory (1,144 words) [view diff] exact match in snippet view article find links to article

Zbl 0012.27010. Boolos, G.; Burgess, J. P.; Jeffrey, R. (2007), Computability and Logic (5th ed.), Cambridge: Cambridge University Press, ISBN 978-0-521-87752-7

PCP (469 words) [view diff] exact match in snippet view article find links to article

default gateways Post correspondence problem, an important problem in computability theory Primary Control Program, an option in OS/360 Principia Cybernetica

♯P (944 words) [view diff] exact match in snippet view article find links to article

hash lemma. Computer programming portal Quantum_computing#Relation_to_computability_and_complexity_theory – Computer hardware technology that uses quantum

SMN (159 words) [view diff] exact match in snippet view article find links to article

tumor Seri Maharaja Mangku Negara, a Malaysian honour S-m-n theorem, a computability theorem regarding programming languages Servicio Meteorológico Nacional

Richard M. Karp (883 words) [view diff] exact match in snippet view article find links to article

combinatorial optimization problems, the identification of polynomial-time computability with the intuitive notion of algorithmic efficiency, and, most notably

BQP (3,518 words) [view diff] exact match in snippet view article find links to article

original on 2022-10-09. L. Adleman, J. DeMarrais, and M.-D. Huang. Quantum computability. SIAM J. Comput., 26(5):1524–1540, 1997. George, Michael Goderbauer

George Boolos (2,185 words) [view diff] exact match in snippet view article find links to article

three editions of the classic university text on mathematical logic, Computability and Logic. The book is now in its fifth edition, the last two editions

Rule-based system (1,196 words) [view diff] exact match in snippet view article find links to article

and Applications (pp. 3-100). Tärnlund, S.Å. (1977). "Horn clause computability". BIT Numerical Mathematics. 17 (2): 215–226. doi:10.1007/BF01932293

Neil D. Jones (345 words) [view diff] exact match in snippet view article find links to article

ISBN 9780262100649. Full text available online. Jones, Neil D. (1995). "Computability and Complexity from a Programming Perspective (MFPS Draft preview)"

Partial algebra (176 words) [view diff] exact match in snippet view article find links to article

on partial algebras. Akademie-Verlag. Horst Reichel (1987). Initial computability, algebraic specifications, and partial algebras. Clarendon Press.

Axiom of dependent choice (950 words) [view diff] exact match in snippet view article find links to article

converse is proved in Boolos, George S.; Jeffrey, Richard C. (1989). Computability and Logic (3rd ed.). Cambridge University Press. pp. 155–156. ISBN 0-521-38026-X

Frode Alfson Bjørdal (584 words) [view diff] case mismatch in snippet view article find links to article

"2015:Third St.Petersburg Days of LOGIC and COMPUTABILITY". "2015:Third St.Petersburg Days of LOGIC and COMPUTABILITY". "The Book "Logic around the World" –

Witness (mathematics) (492 words) [view diff] exact match in snippet view article

theory George S. Boolos, John P. Burgess, and Richard C. Jeffrey, 2002, Computability and Logic: Fourth Edition, Cambridge University Press, ISBN 0-521-00758-5

NUS university professor (273 words) [view diff] exact match in snippet view article find links to article

university professors in NUS. Chong Chi Tat, mathematician in recursion/computability theory; former deputy vice chancellor, deputy president and provost

MOC (303 words) [view diff] exact match in snippet view article find links to article

generator used by the Qt development framework Model of computation, in computability theory Music on Console, a console audio player Mars Orbiter Camera

Separability (245 words) [view diff] exact match in snippet view article find links to article

sets of points in Euclidean geometry Recursively inseparable sets, in computability theory, pairs of sets of natural numbers that cannot be "separated"

Chomsky hierarchy (1,348 words) [view diff] exact match in snippet view article find links to article

ISBN 9781119598701. S2CID 241301126. Kozen, Dexter C. (2007). Automata and computability. Undergraduate Texts in Computer Science. Springer. pp. 3–4. ISBN 978-0-387-94907-9

Weihrauch reducibility (618 words) [view diff] exact match in snippet view article find links to article

(eds.), "Weihrauch Complexity in Computable Analysis", Handbook of Computability and Complexity in Analysis, Cham: Springer International Publishing

NUS university professor (273 words) [view diff] exact match in snippet view article find links to article

university professors in NUS. Chong Chi Tat, mathematician in recursion/computability theory; former deputy vice chancellor, deputy president and provost

Mu (letter) (1,651 words) [view diff] exact match in snippet view article

freely as a variable name. a measure in measure theory minimalization in computability theory and Recursion theory the integrating factor in ordinary differential

Automata (disambiguation) (139 words) [view diff] exact match in snippet view article

Automata may also refer to: Cellular automata, a discrete model studied in computability theory and other disciplines Von Neumann cellular automata, the original

One-instruction set computer (3,772 words) [view diff] exact match in snippet view article find links to article

2017-09-16. Z. A. Melzak (1961). "An informal arithmetical approach to computability and computation". Canadian Mathematical Bulletin. 4 (3): 279–293. doi:10

Method of moments (statistics) (1,934 words) [view diff] exact match in snippet view article

estimators can be computed much more quickly and easily. Due to easy computability, method-of-moments estimates may be used as the first approximation

Alan Selman (663 words) [view diff] exact match in snippet view article find links to article

of several edited volumes, Selman was the coauthor of the textbook Computability and Complexity Theory (with Steve Homer, Springer, 2001; 2nd ed., 2011)

Turing Award (3,581 words) [view diff] exact match in snippet view article find links to article

4, 2023. Retrieved June 3, 2015. Homer, Steven and Alan L. (2001). Computability and Complexity Theory. Springer. p. 35. ISBN 978-0-387-95055-6. Archived

Oracle (disambiguation) (704 words) [view diff] exact match in snippet view article

early computer Oracle machine, or oracle, in complexity theory and computability theory Blockchain oracle, a service that connects smart contracts with

Joint spectral radius (1,511 words) [view diff] exact match in snippet view article find links to article

spite of the negative theoretical results on the joint spectral radius computability, methods have been proposed that perform well in practice. Algorithms

Half-integer (802 words) [view diff] exact match in snippet view article find links to article

ISBN 9783110221848. Boolos, George; Burgess, John P.; Jeffrey, Richard C. (2002). Computability and Logic. Cambridge University Press. p. 105. ISBN 9780521007580. Baez

Newton da Costa (1,551 words) [view diff] exact match in snippet view article find links to article

Jaskowski's Discussive Logic. Non-Classical Logics, Model Theory and Computability, North-Holland Publishing Company, Amsterdam, pp. 37–56, 1977. N.C.A

Naomi Sager (548 words) [view diff] exact match in snippet view article find links to article

Co. p. 2. ISBN 3-11-008244-6. Sager, Naomi, and Nhan, Ngo Than, "The computability of strings, transformations, and sublanguage", pp. 78–120. Chapter in

Dyadic rational (3,895 words) [view diff] exact match in snippet view article find links to article

MR 1137517, S2CID 11758381 Zheng, Xizhong; Rettinger, Robert (2004), "Weak computability and representation of reals", Mathematical Logic Quarterly, 50 (4–5):

Drinker paradox (1,016 words) [view diff] exact match in snippet view article find links to article

Compactness, Omniscience Principles, and the Drinker Paradox" (PDF). Computability in Europe 2010: 2. {{cite journal}}: Cite journal requires |journal=

Sublanguage (581 words) [view diff] exact match in snippet view article find links to article

Berlin: Walter de Gruyter. Sager, Naomi; Nhàn, Ngô Thanh (2002). "The computability of strings, transformations, and sublanguage". In Nevin, Bruce E; Johnson

Unary numeral system (1,251 words) [view diff] exact match in snippet view article find links to article

ISBN 9780385672665. Davis, Martin; Sigal, Ron; Weyuker, Elaine J. (1994), Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science

Herbert Enderton (223 words) [view diff] exact match in snippet view article find links to article

Introduction to Logic. Academic Press. 1972. ISBN 978-0-12-238452-3. Computability Theory: An Introduction to Recursion Theory. Academic Press. 2011.

Albert Muchnik (346 words) [view diff] exact match in snippet view article find links to article

Muchnik's most significant contribution was on the subject of relative computability. He and Richard Friedberg independently introduced the priority method

Vijay Vazirani (860 words) [view diff] exact match in snippet view article find links to article

2002, he has been at the forefront of the effort to understand the computability of market equilibria, with an extensive body of work on the topic. His

PCM, Inc. (1,862 words) [view diff] exact match in snippet view article find links to article

strong relationship with Microsoft. In 1996–1997, the company acquired Computability, a Milwaukee-based company, and Elek-Tek, a Chicago-based company, both

Boolean domain (940 words) [view diff] exact match in snippet view article find links to article

Bibcode:2008slmc.book.....M. Boolos, George S.; Jeffrey, Richard C. (1980). Computability and Logic. Cambridge University Press. p. 99. Mendelson, Elliott (1997)

Leopold Löwenheim (467 words) [view diff] exact match in snippet view article find links to article

"Leopold löwenheim, Life, Work and Early Influence". Provability, Computability and Reflection. Elsevier. ISBN 9780080954967. Brady, Geraldine, 2000

Cristina Sernadas (342 words) [view diff] exact match in snippet view article find links to article

D. Gabbay, and P. Gouveia, Springer, 2008) A Mathematical Primer on Computability (with A. Sernadas, J. Rasga and J. Ramos, College Publications, 2018)

Charles Petzold (1,041 words) [view diff] exact match in snippet view article find links to article

Annotated Turing: A Guided Tour through Alan Turing's Historic Paper on Computability and the Turing Machine (Wiley, 2008) 3D Programming for Windows - Three-Dimensional

Howard Jerome Keisler (513 words) [view diff] exact match in snippet view article find links to article

Memoirs, 1984 Keisler, H. J.; Robbin, Joel. Mathematical Logic and Computability, McGraw-Hill, 1996 Fajardo, Sergio; Keisler, H. J. Model Theory of Stochastic

Series–parallel graph (1,031 words) [view diff] exact match in snippet view article find links to article

1137/0211023. Takamizawa, K.; Nishizeki, T.; Saito, N. (1982). "Linear-time computability of combinatorial problems on series–parallel graphs". Journal of the

Dexter Kozen (792 words) [view diff] exact match in snippet view article find links to article

Springer. ISBN 978-1-84628-297-3. Kozen, Dexter (1997). Automata and Computability. New York: Springer-Verlag. ISBN 978-0-387-94907-9. Kozen, Dexter (1991)

LBA (200 words) [view diff] exact match in snippet view article find links to article

and other macromolecules. Linear bounded automaton, a construct in computability theory Location-based advertising, a form of advertising in mobile telecommunications

Constructible function (918 words) [view diff] exact match in snippet view article find links to article

139. ISBN 978-0-521-88473-0. Homer, Steven; Selman, Alan L. (2011). Computability and Complexity Theory (Second ed.). Springer. ISBN 978-1-4614-0681-5

Tibor Radó (502 words) [view diff] exact match in snippet view article find links to article

Bell System Technical Journal: the busy beaver function and its non-computability ("On Non-Computable Functions"). He died in New Smyrna Beach, Florida

Context-sensitive grammar (3,503 words) [view diff] exact match in snippet view article find links to article

ISBN 978-1-85233-074-3. Davis, Martin; Sigal, Ron; Weyuker, Elaine J. (1994). Computability, Complexity, and Languages: Fundamentals of Theoretical Computer Science

Jack Copeland (1,264 words) [view diff] exact match in snippet view article find links to article

Fastest Computer (Oxford University Press, 2012) ISBN 978-0-19-960915-4 Computability: Turing, Gödel, Church, and Beyond (MIT Press, 2013). ISBN 978-0-262-52748-4

Meaning (psychology) (529 words) [view diff] exact match in snippet view article

shift was the introduction of computation as the ruling metaphor and of computability as a necessary criterion of a good theoretical model. Information is

Thought experiment (8,179 words) [view diff] exact match in snippet view article find links to article

Philosophers (computer science) Halting problem (limits of computability) Turing machine (limits of computability) Two Generals' Problem Broken window fallacy (law

Projective hierarchy (483 words) [view diff] exact match in snippet view article find links to article

Rogers, Hartley (1987) [1967], The Theory of Recursive Functions and Effective Computability, First MIT press paperback edition, ISBN 978-0-262-68052-3

Projective hierarchy (483 words) [view diff] exact match in snippet view article find links to article

Rogers, Hartley (1987) [1967], The Theory of Recursive Functions and Effective Computability, First MIT press paperback edition, ISBN 978-0-262-68052-3

Abel equation (1,032 words) [view diff] exact match in snippet view article find links to article

of holomorphic maps: Resurgence of Fatou coordinates, and Poly-time computability of Julia sets Ph.D. Thesis Classifications of parabolic germs and fractal

Algorithmically random sequence (4,904 words) [view diff] exact match in snippet view article find links to article

intuitive notion of a function being "computable". Like how Turing-computability has many equivalent definitions, Martin-Löf randomness also has many

Random sequence (1,191 words) [view diff] exact match in snippet view article find links to article

and the definition he made relied on the Church Turing Thesis for computability. This definition is often called Mises–Church randomness. During the

Data type (3,407 words) [view diff] exact match in snippet view article find links to article

possible data types are often restricted by considerations of simplicity, computability, or regularity. An explicit data type declaration typically allows the

Log-space reduction (1,358 words) [view diff] exact match in snippet view article find links to article

{\displaystyle O(\log f(n))} . The most important property of logspace computability is that, if functions f , g {\displaystyle f,g} are logspace computable

Turing machine equivalents (2,667 words) [view diff] exact match in snippet view article find links to article

Melzak, Z. A. (September 1961). "An informal Arithmetical Approach to Computability and Computation". Canadian Mathematical Bulletin. 4 (3): 279–293. doi:10

Outline of academic disciplines (4,327 words) [view diff] exact match in snippet view article find links to article

verification) Theory of computation Automata theory (Formal languages) Computability theory Computational complexity theory Concurrency theory VLSI design

Jacques Herbrand (722 words) [view diff] exact match in snippet view article find links to article

mathematician who died in a mountain climbing accident (Gödel-Herbrand) computability thesis: before Church and Turing, in 1933 with Kurt Gödel, they created

Robin Gandy (661 words) [view diff] exact match in snippet view article find links to article

College, Oxford". Wilfried Sieg, 2005, Church without dogma: axioms for computability, Carnegie Mellon University Robin Gandy — The Alan Turing Scrapbook

Semi-Thue system (3,406 words) [view diff] exact match in snippet view article find links to article

1988, ISBN 0-387-13715-7. Martin Davis, Ron Sigal, Elaine J. Weyuker, Computability, complexity, and languages: fundamentals of theoretical computer science

Wang B-machine (515 words) [view diff] exact match in snippet view article find links to article

Melzak (1961) received 15 May 1961 An Informal Arithmetical Approach to Computability and Computation, Canadian Mathematical Bulletin, vol. 4, no. 3. September

Nikolai Shanin (1,580 words) [view diff] exact match in snippet view article find links to article

mathematical logic and proof theory. This work extended into areas such as computability (e.g., Yuri Matiyasevich), algorithmics, computational complexity, and

Takao Nishizeki (562 words) [view diff] exact match in snippet view article find links to article

articles Takamizawa, K.; Nishizeki, T.; Saito, N. (1982), "Linear-time computability of combinatorial problems on series–parallel graphs", Journal of the

Richard Shore (294 words) [view diff] exact match in snippet view article find links to article

The Degrees of Unsolvability: the Ordering of Functions by Relative Computability. In 2009, he was the Gödel Lecturer (Reverse mathematics: the playground

Pavel Tichý (547 words) [view diff] exact match in snippet view article find links to article

(Charles University, 1964), thesis: Vyčíslitelnost ve vztahu k teoriím [On Computability w.r.t. Theories] Docent (Charles University, 1969), thesis: Intensions

Computational topology (1,567 words) [view diff] exact match in snippet view article find links to article

doi:10.1090/S0002-9947-05-03919-X Brown, Edgar H. (1957), "Finite Computability of Postnikov Complexes", Annals of Mathematics (2), 65 (1): 1–20, doi:10

Hyperimmune (61 words) [view diff] exact match in snippet view article find links to article

Hyperimmune may refer to: A hyperimmune set in computability theory Hyperimmunization, the presence of a larger-than-normal number of antibodies Hyperimmune

Indicator function (2,543 words) [view diff] exact match in snippet view article find links to article

Company. Boolos, George; Burgess, John P.; Jeffrey, Richard C. (2002). Computability and Logic. Cambridge UK: Cambridge University Press. ISBN 978-0-521-00758-0

Elaine Rich (309 words) [view diff] exact match in snippet view article find links to article

Knight, 1991; 3rd. ed, with K. Knight and S. B. Nair, 2009) Automata, Computability, and Complexity: Theory and Applications (Prentice-Hall, 2008) Rich