Please enable JavaScript.
Coggle requires JavaScript to display documents.
Models of Computation (Lambda Calculus (Calculi - Very simple programming…
Models of Computation
Lambda Calculus
Calculi - Very simple programming languages not often used in practise. Eg. Turing Machines, Arithmetic
-
-
-
Abstraction - Replacing a λx with a value or function. Replaces every free instance of x in the function
-
-
-
-
Automata
Deterministic Finite Automata (DFA) - Has a single starting state. Each state lists every option of the alphabet. Accepting states are circled
Partial DFA - A DFA where not all options have to be listed, and are regarded as non-accepting
NFA - Can have multiple starting states. At each state, a character can have multiple paths. So an acceptable word is a word that can be mapped to an accepting state in at least one way
-
Kleene's Theorem - Using a regex to create an εNFA, then an NFA then a DFA.
Combining DFA's - Start at the initial state, and build a new DFA, where each state is a set of states from the two DFA's. If one version of a state accepts, and another rejects, then the two languages are not equivalent
-
Turing Machines
Tape - External infinite memory. Has cells which store a single character and a head which points to a specific cell. Head must be returned to the original location after a program finishes executing
-
Return Values - Read, Write x, Left, Right, No-op, Return T/F, Stop
Auxiliary Characters - A set of characters {a', b'} that are used temporarily. So a program can assume there aren't any to begin with and won't be any after
-
2D TM - Has a sheet rather than a tape, with values "Up" and "Down". Must be blank except for one row before and after
Decidability
Church's Thesis - Any decision problem on words that can be solved by an algorithm can be solved on a TM
Computable - Any function that takes a word and returns a word, can be solved in a TM
Reducing Q to P means, given a way to solve P, it is possible to solve Q. If P decidable, then so is Q. If Q undecidable, then so is P
The Halting Problem - Deciding if program P will finish executing or run forever. Proved to be undecidable
Proof - 1. Assume Haltcheck(M, y) which returns T/F is decidable. 2. Hangcheck(M,y) runs Haltcheck and halts if F. 3. Doublehang(y) { Hangcheck(y,y) }. So Haltcheck(DH, DH) will run forever, therefore contradiction
Introduction
-
Searching problem - Searching through a body of text to find an/all occurrences of a word/set of words
Uncountably many languages, therefore they are not all regular
Definitions
-
-
Language - subset of Σ*, set of all accepted words
-
-
Context Free Languages
Countably many languages, uncountably many languages. Eg well bracketed language is non regular
-
-
Ambiguity - A grammar that allows words to be defined in more than one way. Use a derivation tree to test
Complexity
-
-
Basically looks at the number of steps in a program, ignores any actual code
-
P and NP
NP Search Problems - solutions have size in polynomial, and can be checked in polynomial time. Given these two facts, a solution can be found in at least exponential time
Search Problems - Given a problem instance, tries to find a word that relates to it, a solution. If none exists, then returns impossible
NP Completeness - The NP=P problem. Any NP problem can be reduced to an NP-complete one in polynomial time. So if you can solve an NP-complete problem in polynomial time, it is possible to solve all in polynomial
Sets
AxB - All of the elements of A and B, where duplicates are counted once
A+B - All of the elements of A and B. Each subset is tagged, so duplicates are counted
-
Properties of Code
Rice's Theorem - Every semantic property is undecidable. Eg. Whether a program only prints good words. To prove a program is not semantic, find an instance where true and where false, but have the same behaviour
Proof - Reduce the halting problem. Given a property R, there will be a case that has and doesn't. Does halt code have the property? If does: code M that doesn't. F(M) has same properties. If M hangs, then so does F(M), which has same semantics as halt code and therefore is R. Which contradicts so R must be undecidable.