This page gathers the 195 dictionary entries belonging to the domain “Computing theory”, as labelled by Wiktionary. Each word leads to its full entry: definitions, etymology, pronunciation, examples. Page 2 of 2: from “metacompilation” to “Zeno machine”.
- metacompilation noun A computation which involves metasystem transitions from a computing machine to a metamachine which controls, analyzes and imitates the…
- metalearning noun A form of machine learning where automatic learning algorithms are applied to metadata about machine learning experiments, so that the…
- metaspace noun The conceptual space occupied by metaobjects.
- midrise adj Having a zero-valued classification threshold (analogous to a riser of a stairway).
- mixfix adj Being or relating to a kind of operator that can combine any of the infix, prefix, postfix, and closed notations.
- monotype noun In the Hindley–Milner type system, a single specific data type.
- NC noun Initialism of Nick's Class, the complexity class of decision problems solvable in polylogarithmic time using a polynomial number of…
- non-terminal noun A non-terminal symbol in a formal grammar.
- non-terminal symbol noun A symbol in a formal grammar that cannot appear in sentences of the grammar but may eventually be resolved into a sequence of terminal…
- nonblocking adj That does not block; allowing other tasks to proceed immediately rather than having to wait for completion.
- NP-complete adj 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…
- NP-easy adj Solvable in polynomial time by a deterministic Turing machine with an oracle for some decision problem in NP.
- NP-hard adj A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H.
- nugget noun A partial description gleaned from data mining.
- oracle noun A theoretical entity capable of answering some collection of questions.
- oracle machine noun In computability theory, a form of theoretical Turing machine, able to solve even undecidable decision problems in a single operation.
- order statistic tree noun A variant of the binary search tree (or more generally, a B-tree) that supports, in addition to insertion, lookup and deletion, the…
- P-complete adj Describing any problem in the complexity class P to which there exists a polynomial time mapping from any other problem in P.
- pachinko allocation noun In machine learning and natural language processing, a suite of algorithms to determine the thematic structure of a collection of documents…
- paddable adj Capable of being padded; said of a set whose strings can be transformed into infinitely many further strings in the set.
- partial evaluation noun A technique for program optimization by specialization, so as to produce new programs which run faster than the originals while guaranteed…
- Patricia tree noun A radix tree with radix of 2, meaning that each bit of the key is compared individually and each node is a two-way branch.
- piece table noun A data structure consisting of an original document and a series of insertions and deletions referring back to parts of the original or…
- polytype noun In the Hindley–Milner type system, a data type containing variables bound by one or more ∀ (for-all) quantifiers.
- postorder adj Of a tree traversal, recursively visiting the left and right subtrees before the root.
- precedence rule noun A set of rules specifying the order in which parts of an expression are parsed, especially when parentheses are not present.
- prefix coding noun A coding system that uses (typically variable-length) codes that are distinguished by their "prefix property", which requires that there is…
- preorder adj Such that, recursively, the root is visited before the left and right subtrees.
- primitive recursion noun Recursion to a fixed depth.
- probvious adj Able to be shown to hold with very high confidence via heuristic arguments, but not formally provable.
- pseudoalgorithm noun A description of a process that resembles, but is not in fact, an algorithm, as for example by being written in vague pseudocode.
- pseudostate noun An entity that resembles, but is not in fact, a state in a state machine or similar.
- pushdown automaton noun An automaton with finitely many states that can also use one unbounded stack of memory; the automaton may only push, pop, or read the top…
- Q-learning noun A model-free reinforcement learning algorithm to learn a policy telling an agent what action to take under what circumstances.
- quaject noun An object-like data structure containing both data and code (or pointers to code), typically used as an abstraction to manage…
- quantum adj Relating to a quantum computer.
- queuing noun The act of placing something in a queue.
- R-tree noun A kind of tree data structure used to group objects by nearness of location, representing them by their minimum bounding rectangles in the…
- rabbit noun A large element at the beginning of a list of items to be bubble sorted, and thus tending to be quickly swapped into its correct position.…
- radix tree noun A space-optimized trie data structure in which each node that is the only child is merged with its parent.
- random access noun The ability to access any element of a sequence in real time, without having to seek through preceding elements.
- readers-writers problem noun Any of a class of problems in which many concurrent threads of execution try to access the same shared resource at one time, with…
- recursive adj which can be computed by a theoretical model of a computer, in a finite amount of time
- recursive descent noun A kind of top-down parsing involving a set of mutually recursive procedures, each of which implements one of the non-terminals of the…
- recursively enumerable adj Of a set, such that there exists a deterministic algorithm which will list all the items in the set and no others.
- reduction noun A transformation of one problem into another problem, such as mapping reduction or polynomial-time reduction.
- regular expression noun A concise description of a regular formal language with notations for concatenation, alternation, and iteration (repetition) of…
- Reingold-Tilford algorithm noun An algorithm that generates aesthetically pleasing drawings of binary trees (and by extension, n-ary trees).
- rematerialization noun A compiler optimization that saves time by recomputing a value instead of loading it from memory.
- ring noun A hierarchical level of privilege in a computer system, usually at hardware level, used to protect data and functionality (also protection…
- ripple carry noun The situation where a logic circuit uses multiple full adders to add n-bit numbers, with each full adder taking the output of the previous…
- selection sort noun A sorting algorithm that divides the input list into two sublists — items already sorted, and items not yet sorted — and gradually…
- self-balancing adj Of a data structure: able to maintain a small height (number of levels) regardless of insertions and deletions.
- semi-decidable adj 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…
- sentence noun Any of the set of strings that can be generated by a given formal grammar.
- Shellsort noun A sorting algorithm that starts by sorting pairs of elements that are far apart from each other, then progressively reduces the gap between…
- sibling noun A node in a data structure that shares its parent with another node.
- sister noun A node in a data structure that shares its parent with another node.
- skip list noun A probabilistic data structure that allows fast search within an ordered sequence of elements by maintaining a linked hierarchy of…
- sleeping barber problem noun A problem of interprocess communication and synchronization where one process responds to requests from multiple other threads and sleeps…
- smoothsort noun A sorting algorithm based on heapsort but using the Leonardo numbers, tending to perform better than heapsort in cases where the items to…
- Solomonoff induction noun A form of induction, involving Bayes' theorem, that derives the posterior probability of any computable theory, given a sequence of…
- spaghetti sort noun A linear-time algorithm for sorting a sequence of items, analogous to standing a number of strands of spaghetti of different lengths…
- splay verb To rearrange (a splay tree) so that a desired element is placed at the root.
- splay tree noun A self-balancing binary search tree with the additional property that recently accessed elements are quick to access again.
- star height noun A measure of the structural complexity of a regular expression, equal to the maximum nesting depth of stars in the expression.
- state machine noun Ellipsis of finite-state machine.
- subnormal adj denormal
- synchronizer noun An algorithm that can be applied to a synchronous distributed algorithm to produce a version that operates in asynchronous networks.
- tagger noun A program or algorithm that adds tags for purposes of categorization, e.g. grammatical information to words in a document, or genres to…
- terminal noun A terminal symbol in a formal grammar.
- thundering herd noun The undesirable situation where a large number of processes waiting for an event are awoken whenever the event occurs, and then engage in a…
- tile verb To optimize (a loop in program code) by means of the tiling technique.
- tiling noun A technique for optimizing loops by partitioning the iteration space into smaller chunks or blocks that will more easily fit in a cache.
- token bucket noun A fixed-capacity data structure to which tokens or packets are added at a fixed rate; used in algorithms to check whether sufficient tokens…
- tracelet noun A short fragment of the trace of execution of a computer program, used in automated systems that attempt to understand and optimize source…
- transducer noun A state machine that generates output based on a given input.
- transition function noun A function from (state, input symbol) to state describing what state to move to on receiving a given input in a given state.
- tree noun A recursive data structure in which each node has zero or more nodes as children, but does not share children with other nodes.
- treelist noun A list of trees (the data structure).
- trellis noun A kind of graph, used in communication theory and encryption, whose nodes are ordered into vertical slices by time, with each node at each…
- Turing jump noun In computability theory, an operation that assigns to each decision problem X a successively harder decision problem X′ with the property…
- Turing machine noun An abstract computing machine that has a finite number of possible internal states and operates on an infinite memory tape by first reading…
- Turing reduction noun 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…
- Turing tape noun The infinitely long memory tape on which a Turing machine would operate, consisting of individual cells that can be read or written.
- turmite noun A two-dimensional variant of a Turing machine in which the head has an orientation in addition to a position and state.
- turtle noun A small element towards the end of a list of items to be bubble sorted, and thus tending to take a long time to be swapped into its correct…
- type noun A tag attached to variables and values used in determining which kinds of value can be used in which situations.
- undecidable adj Incapable of being algorithmically decided in finite time. For example, a set of strings is undecidable if it is impossible to program a…
- unlimited register machine noun A particular type of theoretical computer, with infinitely many memory cells, called registers, and formal rules to determine the machine's…
- uptree adj Higher in a tree data structure.
- wait-free adj Involving no busy-wait loops or locks for synchronizing with other threads. Able to act immediately without waiting on others.
- wake-sleep algorithm noun A certain unsupervised learning algorithm for neural networks, having separate "wake" and "sleep" phases that attempt to connect the layers…
- X-machine noun A theoretical computer that operates on some fundamental data type X. It is a structurally the same as a finite-state machine, but each…
- Zeno machine noun A hypothetical computational model, related to Turing machines, that would be capable of carrying out computations involving a countably…