adj
(computing theory, of a sequence) Having the property x_0≤⋯≤x_k≥⋯≥x_n-1 for some k,0≤k
n
(optimization) A function whose closed-form expression is not known or does not exist, and whose properties cannot be inferred.
n
(computing theory) A fundamental theorem about the complexity of computable functions, stating that for any complexity measure there are computable functions that are not optimal with respect to that measure.
n
(computing theory) A Turing machine that attains the maximum number of steps performed, or number of non-blank symbols finally on the tape, among all Turing machines in a certain class.
n
(countable) A decision-making method, especially one appropriate for a specialised realm.
n
(computing theory) A real number that informally represents the probability that a randomly-constructed program will halt.
n
(mathematics) A means of representing data and operators in the lambda calculus, by forming them into a mathematical structure embedded in the lambda calculus.
n
(computing theory) A hypothesis about the nature of computable functions, stating that a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine.
adj
(computing theory) Describing a set for which there exists a deterministic algorithm that will list all items not in that set.
n
Constant function, one-valued function (in automata theory) (in particular application causing a reset).
adj
(computing theory, of a problem) That is in a given complexity class and is such that every other problem in the class can be reduced to it (usually in polynomial time or logarithmic space).
n
(computational complexity theory) a set of computational problems of related resource-based complexity
n
(computer science) The study and classification of decision problems by the computational resources—such as time and space—needed by the programs that solve the problems.
n
(computer science) The branch of the theory of computation that studies which problems are computationally solvable using different models.
adj
(mathematics, set theory) Of a countably infinite set, having a computable indicator function.
n
(mathematics, computing theory) Mathematical analysis of computable numbers and functions.
n
(sciences) Any property of an experiment, determined numerically, that does not change under given circumstances.
adj
(object-oriented programming) Using or relating to contravariance.
n
(computing theory) A Turing reduction that runs in polynomial time.
n
Any mathematical relationship between an activity and its cost.
n
(mathematics) A notation for representing terms in the lambda calculus with the purpose of eliminating the names of the variables from the notation.
n
(mathematics) A mathematical constant, denoted by Λ, defined via the zeros of a certain function H(λ, z), where λ is a real parameter and z is a complex variable. H has only real zeros if and only if λ ≥ Λ. The Riemann hypothesis is equivalent to the conjecture that Λ ≤ 0.
adj
(computer science) describing a set for which there exists an algorithm that will determine whether any element is or is not within the set in a finite amount of time.
n
(computing theory) A question in some formal system with a yes-or-no answer, depending on the values of input parameters.
n
(mathematics, informal) A differential equation.
n
(mathematics) An equation involving an ordered sequence of real numbers (a_nₙ₌₁ ᪲) and some of its differences, where the first difference is defined as 𝛥(a_n)=a_n+1-a_n, and the kᵗʰ difference is defined recursively as 𝛥ᵏ(a_n)=𝛥ᵏ⁻¹(a_n+1)-𝛥ᵏ⁻¹(a_n),.
n
(computing theory) One of the three rewrite rules of lambda calculus, which expresses a sort of tautology about function application. The rule says that a lambda abstraction of the form (𝜆x.(fx)) may be rewritten as simply f, provided that x does not occur freely in f (considered by itself).
n
(mathematics) A completion of a mathematical operation; a valuation.
adj
(computing theory) Capable of computing any recursive function.
n
(mathematics, economics) A branch of applied mathematics that studies strategic situations in which individuals or organisations choose various actions in an attempt to maximize their returns.
n
(computing theory) An algorithm for merging the non-distinguishable states of a deterministic finite-state automaton, based on partitioning the states into groups by their behaviour.
n
(computing theory) A polynomial-time algorithm for transforming inputs to one problem into inputs to another problem, such that the transformed problem has the same output as the original.
n
(algebra) A constant or variable the value of which is already determined.
n
(computing theory) A semidecision algorithm for transforming a set of equations (over terms) into a confluent term rewriting system.
n
(computing theory) The complexity of an information object—such as a book or an image—informally defined as the length of the shortest program that produces that information object.
n
(computing theory) A lambda term of the form (𝜆x.t) where x is a variable and t another lambda term. Any free instance of x within t (considered by itself) then becomes bound by the 𝜆x. prefix. It is meant to represent an anonymous function.
n
(computing theory) A well-formed formula in the language of a lambda calculus.
v
(mathematics) Used to assign a value to a symbol.
n
(statistics) The probability that some fixed outcome was generated by a random distribution with a specific parameter.
n
(computing theory) The time complexity, denoted O(n), of an algorithm whose running time increases at most linearly with the size of the input.
n
(probability theory) A theorem which states that the long-term average number L of customers in a stationary system is equal to the long-term average effective arrival rate λ multiplied by the average time W that a customer spends in the system.
n
(computing) The number, obtained by complementing every bit of a given number, which produces all ones when exclusive ored with the given number.
n
(computing) Any of a set of subroutines supplied with a language or system that can be called to perform standard mathematical functions efficiently
n
(computing, robotics) The observation that, contrary to traditional assumptions, reasoning (which is high-level in humans) requires very little computation, but sensorimotor skills (comparatively low-level in humans) require enormous computational resources.
n
(computing theory) Nick's Class, the complexity class of decision problems solvable in polylogarithmic time using a polynomial number of processors.
n
(computing theory) Abbreviation of nondeterministic polynomial, the complexity class of computational problems that a nondeterministic Turing machine can solve in polynomial time.
adj
(computing theory, of a decision problem) That is both NP (solvable in polynomial time by a non-deterministic Turing machine) and NP-hard (such that any (other) NP problem can be reduced to it in polynomial time).
adj
(computing theory) solvable in polynomial time by a deterministic Turing machine with an oracle for some decision problem in NP
adj
(computing theory) An alternative definition restricts NP-hard to decision problems and then uses polynomial-time many-one reduction instead of Turing reduction.
adj
(programming, of a function, procedure, command, etc.) Taking no arguments.
n
Alternative spelling of number-crunching [(computing) Any computing application that requires large amounts of numerical calculation.]
n
(computing) Any computing application that requires large amounts of numerical calculation.
n
(computing theory) In computability theory, a form of theoretical Turing machine, able to solve even undecidable decision problems in a single operation.
n
(computing theory) The set of all problems that are solvable in polynomial time by a deterministic Turing machine
n
(computing theory) The set of such problems.
n
T is a set of transitions.
n
(denotational semantics, domain theory) A domain of nondeterministic and concurrent computations, whose elements are certain subsets of a domain.
n
(computing theory) A reasonable proof of a computational theorem or conjecture obtained via a randomized algorithm.
n
(computing theory) A description of a process that resembles, but is not in fact, an algorithm, as for example by being written in vague pseudocode.
adj
(computing theory) Abbreviation of recursively enumerable. [(computing theory) Of a set, such that there exists a deterministic algorithm which will list all the items in the set and no others.]
n
(computing theory) The ability to access any element of a sequence in real time, without having to seek through preceding elements.
n
(computing theory) Abbreviation of "recursively enumerable"; the class of decision problems for which a 'yes' answer can be verified by a Turing machine in a finite amount of time.
n
(mathematics) The act of defining an object (usually a function) in terms of that object itself.
n
(logic) A branch of mathematical logic studying computable functions and Turing degrees, concerned with questions such as "What does it mean for a function on the natural numbers to be computable?" and "Can noncomputable functions be classified into a hierarchy based on their level of noncomputability?".
adj
(computing theory, not comparable, of a set) whose characteristic function is recursive (4)
adj
(computing theory) Of a set, such that there exists a deterministic algorithm which will list all the items in the set and no others.
n
(computing theory) A concise description of a regular formal language with notations for concatenation, alternation, and iteration (repetition) of subexpressions.
adj
(computing theory) Of a set, such that there is a deterministic algorithm such that (a) if an element is a member of the set, the algorithm halts with the result "positive", and (b) if an element is not a member of the set, (i) the algorithm does not halt, or (ii) if it does, then with the result "negative".
n
(computing theory) A method for parsing mathematical expressions specified in infix notation.
n
(computer science) A measure of the amount of space, or memory required by an algorithm to solve a given decision problem. An informal analogy would be the amount of scratch paper needed while working out a problem with pen and paper.
n
(mathematics, computing) A subsidiary iteration
n
(mathematics, economics, dated) game theory.
n
(computer science) the amount of time an algorithm requires to run, as a function of the amount of input, measured in such a way as to ignore constant terms and multiplication by constant terms
n
(computing theory) A function from (state, input symbol) to state describing what state to move to on receiving a given input in a given state.
n
Alan Turing (1912–1954), a British logician and early computer scientist.
adj
(computing theory) Equivalent in power to a universal Turing machine; equivalently, functionally complete.
n
(mathematics) Any function whose value may be computed using a Turing machine.
n
(computer science, logic) A measure of the level of algorithmic unsolvability of the decision problem of whether a given set of natural numbers contains any given number.
n
(computing theory) In computability theory, an operation that assigns to each decision problem X a successively harder decision problem X′ with the property that X′ is not decidable by an oracle machine with an oracle for X.
n
(computing theory) A reduction that solves a problem if the solution to another problem is already known, i.e. an algorithm that could be used to solve A if it had available to it a subroutine for solving B.
n
(computing) The situation in which a programming language is only minimally Turing complete, so that "everything is possible but nothing is easy".
adj
Alternative spelling of Turing complete. [(computing theory) Equivalent in power to a universal Turing machine; equivalently, functionally complete.]
n
(mathematics, computer science) A branch of mathematical logic and theoretical computer science concerned with types.
n
(computing theory) A Turing machine capable of simulating the behavior of any Turing machine.
adj
(programming) Covariant and/or contravariant.
n
(computing theory) A hypothetical computational model, related to Turing machines, that would be capable of carrying out computations involving a countably infinite number of algorithmic steps.
n
(cryptography) An interactive method for one party to prove to another that a (usually mathematical) statement is true, without revealing anything other than the veracity of the statement.
n
(mathematics) A mathematical model of the practical signal reconstruction done by a conventional digital-to-analog converter, describing the effect of converting a discrete-time signal to a continuous-time signal by holding each sample value for one sample interval.
Note: Concept clusters like the one above are an experimental OneLook
feature. We've grouped words and phrases into thousands of clusters
based on a statistical analysis of how they are used in writing. Some
of the words and concepts may be vulgar or offensive. The names of the
clusters were written automatically and may not precisely describe
every word within the cluster; furthermore, the clusters may be
missing some entries that you'd normally associate with their
names. Click on a word to look it up on OneLook.
Our daily word games Threepeat and Compound Your Joy are going strong. Bookmark and enjoy!
Today's secret word is 8 letters and means "Believable and worthy of trust." Can you find it?