Flashcards
LIMITS OF COMPUTATION
Cards in this deck (22)
- 1What makes a programming language an acceptable choice for effective procedures?If a self-interpreter can be written in the language itself.
- 2What is a self-interpreter equivalent to?A universal program.
- 3How can one prove that the halting problem is undecidable?With diagonalisation.
- 4Which complexity class do all effective procedures belong to?P
- 5What is a WHILE-computable (partial) function on trees?One that can be implemented in WHILE.
- 6What is the definition of the halting problem?
- 7What is the membership test of the Halting set HALT?
- 8What does it mean if a problem is semi-decidable?It means that only part of a decision procedure can be made to solve it.
- 9Name problems in PParsing, Primality testing, Shortest Paths, Min-Cut & Max-Flow, the Postman problem,
- 10Name problems not in PTSP, Vehicle Routing Problem, the Graph Colouring Problem, Max-Cut Problem, 0-1 Knapsack Problem, Integer Programming Problem
- 11What is a verifier?A program that can check whether a candidate solution to a problem is valid in polynomial time
- 12What is NTM or NP^TM?Non-deterministic Turing Machine
- 13How can one prove the decidability of a set?If the set itself and its complement are both semi-decidable, then the set is decidable
- 14How can one prove that P is contained in NP?With the construction of a nondeterministic Turing machine which simulates a polynomial program verifier for any problem known to be in P by guessing the certificate nondeterministically
- 15What is a reasonable notion of computation?This means that a notion of computability must be powerful enough to express Turing machines
- 16What is circular compilation?It is the compilation of compilers such as:
c1 -> c2 -> c3 -> c4 -> c1 - 17What is a WHILE-semi-decidable set?It is a set for which
an approximation of the membership test can be computed by a WHILE-program
that may not terminate if the answer is supposed to be false - 18How can we show that the Halting problem (or set) is semi-decidable?
- 19What is the implication of Kleene’s recursion theorem?any acceptable programming system is “closed under recursion”.
- 20How can recursion be achieved?recursion can be done by reflection
- 21What is a specialiser?A specialiser is a program which takes as input another program that takes two or more inputs and partially evaluates it such that the output is the same program with the same semantics, but one with fewer inputs which also runs faster. This is only possible when the inputs are known.
- 22What does 'm' and 'n' stand for in the S-n-m theorem?The number m refers to the number of arguments provided for specialisation, whereas number n refers to the number of arguments that remain after specialisation
Information
- Description
- Flashcards on LIMITS OF COMPUTATION, created by Zenos Pavlakou on 09/05/2019.
- Created by
- Zenos Pavlakou · May 2019
- Updated
- May 15, 2019
- Views
- 1
- Rating