Name: Indika
Ediriwickrama
This essay aims to give a summary of the knowledge acquired during the Computing Theory subject. This essay will touch upon the following topics:
Complexity will discuss how ``expensive'' it will be to approach various computing problems by looking at ``physical'' costs associated with the problems.
There is no better example of a complex problem than crypotgraphy. This section will discuss the relationship between complexity and cryp tography.
Grammars is basically how a computing language is formed. The reasoning behind the way the different computing syntaxes are formed.
Automata deals with building machines that can parse Grammar
Computability will touch upon different types of ways of getting a solution for any given computing problem, and explain how some problems have no solution.
During the 1960's, as computers were more commonly used to solve problems, and as problem sizes grew, it was recognized that the classification of problems provided by ``Computability theory'' was not sufficient: Some problems could be solved, but the time or storage space needed to solve them grew so quickly (as input size increased) that the algorithms available to solve them were of no practical use.
The objective of complexity theory is, to classify problems according to whether they can be solved efficiently using computers or not and to estimate the cost of computing (how much storage, processing power required). There for the theory of decidability (Algorithmic) came in to play an important part in computer science. Theory of decidability shows us that there are some problems we cannot possibly be solved by a computer, there are others unlikely to be solved by computer but which are not theoretically un-decidable and there are some problems that we can't find and algorithm for.
Suppose we have a problem to be solved, is there a algorithm for the problem? If we manage to find finite set of instructions chosen from fixed set of instructions which satisfies the following,
Definiteness- each instruction is clear and unambiguous
Effectiveness- every instruction is sufficiently basic so that it can be carried out mechanically in a finite amount of time.
Finiteness- for every input the algorithm terminates after execution of a finite number of instructions
Correct output- For every input the algorithm outputs a correct answer to the input.
We say that the problem is solvable, decidable or computable else we say the problem is unsolvable, un-decidable or incomputable.
For some problems we can come up with several algorithms so we have to compare them and find the best one, Ho w do we compare algorithms?
We compare algorithms under two criteria�s
#Space complexity (Space requirement) - Space (memory) is becoming more and more
less expensive and its not taken as limited resource
#Time complexity (Running time) - "Hardware speed tend to double every two years"
(Moors law), speed of the computer is expensive and
Limited for the given time
Note- these two criteria�s are also used to measure the cost of the program as well.
We use two methods to measure the time complexity-
# Average case analysis- expected time the program might take to execute/run. This
might sometimes be useful but it is very difficult to decide as
we are left with the question what is average and how often we
have to face worst cases.
#Worst case analysis- Maximum time the program could take considering the worst input it takes.
We use the rate of growth of the algorithm to measure the time complexity
under worst case analysis, and we denote it with the big O notation.
We usually consider the exponential algorithms and worse as intractable (in computable) these are used in cryptography, next topic of �Computer Theory". but sometimes we have to accept algorithms witch are of exponential complexity or something in between. for example:- (1/55)2^n < 1000n^(2).
Example of tractability
Its Obvious enough that not all algorithm are solvable. A Polynomial , Exponential and Factorial rate of growth will have a limitation to its problem. When the value input is too great (ex: n=99), you will definitely find it hard to solve, or maybe it�s even almost impossible to solve. Whereas the slower growing rate such as logarithmic , linear , quadratic and cubic are tractable.
Time estimated for 2 operations/millisecond
|
No |
Algorithm |
N=10 |
N=100 |
N=200 |
N=300 |
N=400 |
|
1 |
O (log N) |
0.005s |
0.01s |
0.014s |
0.016 |
0.017 |
|
2 |
O ( N ) |
0.05s |
0.5s |
1s |
1.5s |
5s |
|
3 |
O ( N2) |
0.5s |
5s |
200s |
450s |
800s |
|
4 |
O ( N r) r=10 |
I year |
3 x 10 7 years |
9 x 1015 years |
5 x 1018 years |
1 x 1020 years |
|
5 |
O ( N! ) |
|
|
|
|
|
When we are solving less complex or non difficult problems, we usually write programs to generate solutions, but how do we solve which are of high complexity? We use different approach when solving this kind of problems. We determine if one of the possibilities is a solution, in other since checking the answer rather then finding one. This sort of approach is known as nondeterministic approach/ non-determinism.
#P- problems: - if there�s a problem decidable in polynomial time and if there�s a
program which solves the problem with time complexity
of O(n^r) where r is a natural number independent of n. the class of all such problems is denoted as P.
#NP- problems :- if there�s a problem decidable in nondeterministic polynomial time
and if there�s a program which solves the problem with time
complexity of O(n^r) where r is a natural number independent of n. the
class of all such problems is denoted as NP.
Problem Reduction: - When solving NP type of problems we could
reduce problems to known problems and solve them to get the
answer, this method is known as Problem Reduction.
NP complete: - If we can reduce NP problems into each other in polynomial time and
there for the polynomial solution for one such problem is a solution for
all of them, if these NP problems represent completely the whole set ,
they are called NP-complete.
Just a simple illustration which space NP might fall in
the art or science encompassing the principles and methods of transforming an intelligible message into one that is unintelligible, and then retransforming that message back to its original form
The two main purposes in cryptography �
Conceal the context of some message from all except the sender and recipient (privacy or secrecy), and/or verify the correctness of a message to the recipient (authentication).
The two methods in cryptography are-
*Private-Key Encryption Algorithms-
a private-key (or secret-key, or single-key) encryption algorithm is one where the sender and the recipient share a common, or closely related, key. All traditional encryption algorithms are private-key
*Public-key (or two-key) Encryption Algorithms �
Involves the use of two keys: a public-key, which may be known by anybody, and can be used to encrypt messages, and verify signatures .a private-key, known only to the recipient, used to decrypt messages, and sign (create) signatures
theory -
there is a public encryption key E which is published and there is a private decryption key D which is kept secret. In any case D is not deducible from E . The sender encrypts the secret message M using his public key and passes it to the receiver. E (D (M)) On receiving the message the receiver uses his decryption key D to decrypt the secret message. D (E (M)) Hence the whole procedure involves the following equation.
E (D (M))= D (E (M))=M
Brief history of encryption �
Steganography or secret writing was probably the first widely used for secure communication. The secret text was hidden by using variety of techniques. For example:
Ancient Ciphers
Julius Caesar used a cipher which moved each letter of the alphabet to the letter three to the right in the predetermined order of the letters of the alphabet, that is: a �D, b �E, . . ., and z �C. The shift cipher is symmetric, knowing the encryption key it is easy to obtain the decryption key. it will always encrypt a letter the same way for the same key (monoalphabetic). To break the code we only require to examine at most is 25 keys.
Monoalphabetic Ciphers
A major drawback of shift ciphers is that the key space is very small, and thus, the system is vulnerable. We can increase the key space dramatically by applying an arbitrary permutation on the alphabet instead of shifting letters. These form of ciphers are cold �Monoalphabetic Ciphers�. The key space of this is 26! And is harder to break then shift ciphers.
Playfair Cipher
This is a multiple-letter encryption cipher. It is based on the use of a matrix. of letters. The matrix is constructed by filling in the letters of the keyword (minus duplications), followed by the remaining letters in alphabetic order.
Hill Cipher
Almost the same as play-fair cipher except that this uses much larger matrix.
Polyalphabetic Ciphers
Transposition Ciphers
Rotor Machines
The basic principle of the rotor machine is that multiple stages of encryption can produce an algorithm that is significantly more difficult to cryptanalysis. If we associate each input and output pin with a letter of the alphabet, then a single cylinder defines a monoalphabetic substitution. The power of the rotor machine is depends on the use of multiple cylinders, in which the output pins of one cylinder are connected to the input pins of the next.
Examples of machine ciphers-
Jefferson cylinder, developed in 1790s, comprised 36 disks, each with a random alphabet and the order of disks was used as the key.
Wheatstone disc, originally invented by Wadsworth in 1817, but developed by Wheatstone in 1860's, comprised two concentric wheels used to generate a poly-alphabetic cipher.
Enigma Rotor machine, one of a very important class of cipher machines, heavily used during 2nd world war, comprised a series of rotor wheels with internal cross-connections, providing a substitution using a continuously changing alphabet.
Modern Private Key Ciphers
Modern private key ciphers consider the message as a sequence of bits. (eg as a series of ASCII characters concatenated) and these have two broad families of methods.
Stream ciphers- this process the message bit by bit (as a stream). add bits of message to random key bits. This requires as many key bits as message there for this method is difficult in practise The most famous of these is the �Vernam cipher� (also known as the one-time pad) invented by Vernam.simply
Block ciphers - in a block cipher the message is broken into blocks, each of which is then encrypted (ie like a substitution on very big characters - 64-bits or more) most modern ciphers we will study are of this form.
1949 Claude Shannon introduced the idea of substitution-permutation (S-P) networks, which now form the basis of modern block ciphers
Substitution Operation
a binary word is replaced by some other binary word and the whole substitution function forms the key. There for if we use n bit words, the key is 2^(n)!bits, grows rapidly. These 2^(n) addresses, we call them S-boxes.
Permutation Operation
a binary word has its bits reordered (permuted) and the re-ordering forms the key. if use n bit words, the key is n!bits, which grows more slowly, we call these addresses as P-boxes. Shannon combined these two primitives; he called these �mixing transformations�
Shannons mixing transformations are a special form of product ciphers where
S-Boxes - provide confusion of input bits
P-Boxes - provide diffusion across S-box inputs
in general these provide the following results:-
Avalanche effect - where changing one input bit results in changes of approx half
the output bits
Completeness effect - where each output bit is a complex function of all the
input bits
in practise we need to be able to decrypt messages, as well as to encrypt them, hence either we have to define inverses for each of our S & P-boxes, but this doubles the code/hardware needed, or define a structure that is easy to reverse, so can use basically the same code or hardware for both encryption and decryption.
Lucifer is the first public ally known example of a practical substitution permutation cipher. It was developed by Horst Feistel at IBM labs. This uses 128 bit data block and 128 bit keys.
in May 1973, and again in Aug 1974 the NBS (now NIST) called for possible encryption algorithms for use in unclassified government applications, so IBM submitted their Lucifer design after following a period of redesign and comment it became the Data Encryption Standard (DES). One of the largest users of the DES is the banking industry, particularly with EFT, and EFTPOS. Today DES is declared to be insecure as rapid advances in computing speed have rendered the 56 bit key is not secure enough. The DES has also been theoretically broken using a method called Differential Cryptanalysis; however in practice this is unlikely to be a problem (yet). Possible Techniques for Improving DES are multiple enciphering with DES, extending DES to 128-bit data paths and 112-bit keys and extending the Key Expansion calculation.
Modern Public-key (or two-key) cryptography
This method involves the use of two keys: a public-key, which may be known by anybody, and can be used to encrypt messages, and verify signatures. A private-key, known only to the recipient, used to decrypt messages, and sign (create) signatures. The way this operates is, B [the recipient] generates e and d, and announces e [the encryption key] openly: So A [or anyone else] can generate [and, if necessary, broadcast] n = E (e, m). But only B [who is the only person to know d] can generate the decrypted message p = D (d, n) from n. e and d are functionally related, because m = D (d, E (e, m)) for every possible message m -- that is, every possible message can bbe obtained by decrypting its encryption. To use the same notations to describe functions which generate keys as their results, We invent d, the secret key, `at random', and use this function (function f). to generate e = f(d). For this to work, f must satisfy:
� f is in P, so that the calculation of e is tractable.
� f -1 is not in P, so that d = f -1(e) is an intractable calculation.
� f is bijective,
An f with these properties is said to be a one-way or trapdoor function.
Since e = f(d) is tractable, f -1 is in NP. For, if an oracle guesses d, then we can verify by computing e that d indeed was the secret key. If NP = P, then there are no trapdoor functions.
One of the problems with public-key encryption is that anyone can send an encrypted message but Since D (d, E (e, m)) = m for all m, it follows that E (e, D (d, E (e, m))) = E (e, m) for all m, by encrypting both sides, and hence that E (e, D (d, x)) = x for many x. The commonest algorithms used in practice, this last equation will hold for all x, that is, encryption and decryption `commute'. So, the idea is that the possessor and only the possessor of the decryption key can send a message which encrypts to the original. So A too can have keys d' and e' = f(d'), where e' is freely announced; A's `signature' is the decryption D (d', m') of some suitable message m', which can change with every message. Examples�
Best known and widely regarded as most practical public-key scheme was proposed by Rivest, Shamir & Adleman in 1977: its security relies on the difficulty of calculating factors of large numbers. The security of the RSA scheme rests on the difficulty of factoring the modulus of the scheme.RSA is costly comparing to the other forms of encryption, especially when the key size get larger. And also it�s a victim of a successful search for an efficient factorization algorithm.
Zero-knowledge proofs
Zero-knowledge proof; this is a probabilistic proof that you know something without revealing what it is that you know.
Every problem in NP has a zero-knowledge proof -- if necessary by first transforming the original problem.
As a conclusion we could say that Cryptography always relies on the high complexity problems and algorithms,factorials. in the older days and here in modern days too.
A grammar consists of a series of rules for forming sentence fragments that, when used in combination; determine the set of well-formed (grammatical) sentences. We will be concerned here only with one, particularly useful form of grammar, called a context-free Grammar. The idea of a context-free grammar is that the rules are specified to hold independently of the context in which they are applied. This clearly limits the expressive power of the formalism, but is powerful enough to be useful with computer languages. in other words
Grammar is concerned with specification of syntax rules for a programming language. It is a way to tell a computer what language is being used and whether the constructs are legal or not. grammar is used to make sure that a series of "words" in certain sequence can be interpreted in a standard way.
A language is a set of symbols that can be combined together in a particular way to give the strings of the language.
There are four types of grammar. The Chomsky hierarchy categorized the grammar in the following order:
1) Regular Grammar
2) Context Free Grammar
3) Context Sensitive Grammar
4) Unrestricted Grammar
A character, glyph, mark. An abstract entity that has no meaning by itself,
often called uninterpreted. Letters from various alphabets, digits and special characters are
the most commonly used symbols.
A finite set of symbols.
An alphabet is often denoted by
Σ= Finite set of symbols, for example Σ= {a,b}, yet can be given any name.
B = {0, 1} Says B is an alphabet of two symbols, 0 and 1. C = {a, b, c}
Says C is an alphabet of three symbols, a, b and c.
Sometimes space and comma are in an alphabet while
other times they are meta symbols used for descriptions.
A finite sequence of symbols from an alphabet..
A null string is a string with no symbols (Empty String)
e (e = symbol (empty string whereas � = empty set)Σ* = set of all strings over alphabet ,
Vertical bars around a string indicate the length of a string expressed as denoted by | x | (like the cardinality symbol) Concatenation of Strings: denoted by x � y or x � y or xy.
A set of strings from an alphabet. A language over an alphabet Σis a set of strings over Σ
(i.e a subset of Σ*, where Σ* = set of all strings over the alphabet). The set may be empty, finite or infinite.There are many ways to define a language.Because a language is a set of strings, the words language and setare often used interchangeably in talking about formal languages.
L(M) is the notation for a language defined by a machine M.The machine M accepts a certain set of
strings, thus a language. L(G) is the notation for a language defined by a grammar G.
The grammar G recognizes a certain set of strings, thus a language.
M(L) is the notation for a machine that accepts a language. The language L is a certain set of strings.
G(L) is the notation for a grammar that recognizes a language.The language L is a certain set of strings.
The union of two languages is a language. L = L1 L2
The intersection of two languages is a language. L = L1 L2
The complement of a language is a language. L = Σ* - L1
The difference of two languages is a language. L = L1 - L2
A set of strings from an alphabet.
The set may be empty, finite or infinite.
The building blocks of regular languages are symbols, concatenation of
symbols to make strings (words), set union of strings and Kleene
closure (denoted as *, also called the Kleene star,)
Informally, we use a syntax for regular expressions.
using Σ as the set {0, 1} (an alphabet of two symbols)
01110 is a string starting with the symbol 0 and then concatenating
1, then 1, then 1, and finally concatenating 0.
(01+10) is a union of the two strings 01 and 10. The set {01, 10}
(00+11)* is the Kleene closure of the union of 0 concatenated with 0 and
1 concatenated with 1.
The Kleene closure (star) is defined as the concatenation of
none, one, two, or any countable number strings it applies to.
kleene star (*) :
L* = {w1...wn : n 0, w1,...,wn L} = set of all strings obtained by concatenating
zero or more strings from L.
(w)+ is a shorthand for (w)(w)* w is any string or expression and the
superscript plus, + , means one or more copies of w are in the set defined
by this expression.
A grammar is defined as G = (V, T, P, S) where:
V is a set of symbols called variables, typically S, A, B, ...
T is a set of symbols called terminal, typically 0, 1, a, b, ...
P is a set of productions
S is the starting or goal variable from V
The productions P are of the form:
A -> w
Where A is a variable
w is any concatenation of variables and terminals
A grammar is defined as G = (V, T, P, S) where:
V is a set of symbols called variables, v1, v2, ... ,vn
T is a set of symbols called terminal, t1, t2, ,,, ,tm
P is a set of productions
S is the starting or goal variable from V
The productions P are of the form:
A -> w
A -> wB
Where A and B are variables
w is any combination terminals, may be empty string
A set of strings from an alphabet.
The set may be empty, finite or infinite.
A grammar G = (V, T, P, S) with the productions restricted to:
A grammar G = (V, T, P, S) with the productions, P, restricted to the form:
variable -> terminal variable(s)
A -> a alpha where A is a variable in V, a is a terminal in T and
alpha is none, one or more variables in V.
A grammar G = (V, T, P, S) with the productions restricted to the forms:
variable -> variable variable
variable -> terminal
A -> B C A, B and C are variables in V and exactly two variables are on the right
A -> a A is a variable in V and a is exactly one terminal symbol in T.
Given a CFG G=(V, T, P, S) and a string x in T*, is x in L(G)?
The CYK Algorithm uses dynamic programming (from 441 algorithms course)
to provide a |x| cubed time algorithm to answer this question.
The languages, sets, accepted by Turing machines and unrestricted grammars.
The sets, languages, that can be generated (enumerated) where all strings
in the set, language, of a given length can be generated.
Usually the enumeration is strings of length 1, then strings of length 2,
and so fourth. there may be no strings for some lengths.
In some cases, generate ^n and pass each string to a machine or
grammar. The accepted strings are the strings of length n.
If both a set and its complement are recursively enumerable, then the
set is recursive.
Type 0, Grammars that generate r.e. sets
and characterize the r.e. languages
Unrestricted grammars of the form G = (V, T, P ,S)
The restriction is removed from the form of the productions.
Type 1, Grammars that characterize context sensitive languages.
Type 2, Grammars that characterize context free languages.
Type 3, Grammars that characterize regular languages.
A parse tree is a tree form of the derivation of a sentence in a context-free language (a language described by a context-free grammar
Ambiguous grammars
If a sentence of a context-free grammar can be represented by more than one parse tree, the grammar is said to be ambiguous.
To get rid of the ambiguity
a) add productions/non-terminals
b) external rules: precedence, binding, etc.
elaborating on Parsing.
Parsing � Determine all possible strings in a context free grammar , Multiple Derivations , input must be determined even if there is no derivation for the grammar . Some grammars allow deterministic parsing
There are altogether 2 different parsing method which is
The top down parsing and bottom up parsing.
Top-Down parsing
Left derivation from S with choice of rule guided by w-(generates leftmost derivation of w guided by w . It start from the start symbol of the grammar ).
Bottom-Up Parsing
Construct a right most derivation in reverse by doing the leftmost production backwards-(generate in reverse order rightmost derivation of w � S guided by rules of G (grammar) .).
LR(K) Left to right
Rightmost derivation
K - lookahead tokens
LR(0) Bottom up (shift-reduce) parsing with no lookahead.
We decide to shift or reduce based on what we have already seen
A general term for an automata.
A machine could be a Turing Machine, a pushdown automata,
a finite state machine or any other restricted version of a Turing machine.
Finite state machine consists of two parts input/output and a processor.
The finite state machine takes in a input parses it reads through the input with the help of processor and then gives the output. e.g coke machine.
M = (Q, Σ, λ, q0, F) is a definition of a Finite Automata.
Where Q a finite set of states often called q0, q1, ... , qn or s0, s1, ... , sn.
q0 the initial state from the set Q. By definition this is the state the automata is in when it starts.
The automata gets the first symbol from the input, then goes from the starting state to the state designated
by the transition function. F a set of final states from the set Q. Final states are also known as
accepting states. The machine stops after the last input symbols is read and the corresponding state
transition occurs. If the machines state when stopped is in F then the machine is said to accept the input
string. F can be a null set in which case only the empty language is accepted. There is no requirement,
in general, that any final state be reachable. A machine defines a language, the set of all strings accepted by
the machine. This language is usually denoted L(M). The machine that accepts a language L
is usually denoted M(L).
Unlike DFA, NFA has multiple starting states and accepts multiple or no transition from a state. If there are no transitions then the machine halts giving a failure without processing the rest of the input. Though DFA and NFA are of the same power as they both correspond to a same regular language and NFA can be converted to DFA.
M = (Q, Σ, λ, q0, F) is the same as for deterministic finite automata
above with the exception that delta can have sets of states.
A string is accepted if any sequence of transitions ends in a Final state. There could be more than one
sequence of transitions that end in a Final state.
Any NFA can be converted to a DFA but the DFA may require exponentially more states than the NFA.
Finite State Machines are not powerful enough as they are not able to form some simple languages.
They can only represent regular languages. There are much more powerful machines
e.g. Pushdown Automata, Turing Machine, than the FSM.
Push Down Automata, PDA, are a way to represent the Context Free Languages,
By themselves PDA's are not very important but the hierarchy of Finite State Machines with
corresponding Regular Languages, PDA's with corresponding CFL's and
Turing Machines with corresponding Recursively Enumerable Sets (Languages),
is an important concept.
PDA uses a stack to remember the input string. Therefore in order for a input string to be valid it should end in the final state and should have stack empty. All the regular grammars can be represented using FSM and all the CFG can be represented using PDA.They have the memory space to keep a track of languages of the
form { wwR | w � {a , b}*)
There are few limitations of PDA. They are as powerful as context-free grammars but it was not able to recognize {anbncn | n >= 0} and they had limited memory.
More powerful machines called Turing Machine were invented by Alan Turing in 1936 which are the machines which have multiple stacks and infinite memory.
A turning machine consists of a head, a state register and an action table. The head reads and writes symbols on a tape which is assumed to be divided into cells that contain a symbol from some finite alphabet consisting of a blank symbol and one or more other symbols. The turning machine is supplied with as much tape as it requires for its computation. The second part, the state register, as the name suggests, stores the state of the turning machine like the start state, stop state and the in-between states. The action table tells the machine what symbol to write and how to move the head. New states of the machine are also shown by the action table. The most powerful kind of Turing Machine are the quantum computers.
Turing machines are the most powerful machine in the modern time. Thus anything which a Turing machine cannot perform computers as well cannot perform.
A Turing machine, named after A. Turing, is defined by
M = (Q, Σ, γ, λ, q0, B, F)
A Turing Machine computes a value rather than recognizing a language,
and leave the computed value on the tape and halts.
It is possible for a TM to never halt on some input strings that are not in the language it accepts or on input
values for which it is not a complete function.
The set of all Turing machines is countable. Thus there exists real numbers that can not be accepted by
any Turing machine.
Turning machines believed to be the most powerful turning machine of all
It is possible to code the definition of every Turing machine as a string of
characters.
A Universal Turing Machine is then a Turing machine that has on its input
tape a definition of some Turing machine and a string. The Universal
Turing Machine simulates the Turing machine defined on its input tape and
accepts the string on its input tape if and only if the simulated Turing
machine would accept the string.
One UTM can simulate another UTM that is simulating a TM with an input string.
The Turing machine restricted to a number of moves bounded by a
fixed polynomial in n, p(n), where n = |x|, n is the length of the
input string. The machine must accept all strings in a language in
polynomial time in order to be in P.
P is a set of languages, also called a class of languages.
Change the deterministic delta transition table to a nondeterministic delta
transition table and the TM represents a class of languages that are
believed to be different from the language class P.
NP is a set of languages, also called a class of languages.
Computability
This is a mathematically unprovable belief that a reasonable intuitive
definition of "computable" is equivalent to the list provably equivalent
formal models of computation:
Turing machines
Lambda Calculus
Post Formal Systems
Partial Recursive Functions
Unrestricted Grammars
Recursively Enumerable Languages
Believed to be the most powerful formal method of computation.
A basic Turing machine is a model for studying computation.
Turing machines can solve decision problems and compute results based
on inputs. When studying computation we usually restrict our attention
to integers. Since a real number has infinitely many fraction digits we
can not compute a real number in a finite time. Rational numbers a
approximations to real numbers are equivalent and can be put in
one-to-one correspondence with the integers.
The "Halting Problem" is a very strong, provably correct, statement
that no one will ever be able to write a computer program or design
a Turing machine that can determine if a arbitrary program will
halt (stop, exit) for a given input.
The Halting Problem says that no computer program or Turing machine
can determine if ALL computer programs or Turing machines will halt
or not halt on ALL inputs. To prove the Halting Problem is
Decision problems are stated as questions where the answer is binary,
0 or 1, False or True, No or yes, Reject or Accept and so forth.
A formally stated problem is Unsolvable
if no Turing machine exists to compute the solution.
A formally stated problem is provably unsolvable
if it can be proved no Turing machine exists to compute the solution.
A problem is Undecidable if no total recursive function
and thus, no Turing machine that always halts, can be constructed
to decide the problem, usually true or false.
Self evaluation
I believe I have thorough knowledge of the subject after writing this essay.
I have tried my level best to make the essay concise an to the point. My weakness in the subject is
grammar, automata and computability .
Elements of the theory of computation - Lewis, Harry R
Languages and machines :
an introduction to the theory of computer science - Sudkamp, Thomas A
The language of machines : an introduction to computability and formal languages
Floyd, Robert W
Programs, machines, and computation : an introduction to the theory of computing-
Clark, K. L. (Keith L.)
Automata, languages, and machines- Eilenberg, Samuel
Cryptography and computational number theory - Carl Pomerance
Cryptology : Machines history & Methods - David Kahn
Introduction to Automata theory, Languages, and Computation - John E Hopcroft
Computability: Computable functions, logic, and the functions of Mathematics- Richard L Epstein
An introduction to Formal Languages and Automata - Peter linz
Walker, H.M. Limits of Computing [webpage] (1999); http://www.mathcs.richmond.edu/ jkent/courses/cs105_may_1999/limits.pdf
Dakin, R. The Travelling Salesman Problem [webpage] (1997); http://www.pcug.org.au/ dakin/tsp.htm
Leahy, L. Problem Complexity [PowerPoint Slide] (2000); http://www.cc.gatech.edu/fac/Bill.Leahy/cs1311/cs1311lecture28wdl.ppt
Weisstein, E.W. NP-Problem from Math World [webpage] (1999); http://mathworld.wolfram.com/NP-Problem.html
References RSA Laboratories. RSA Laboratories' Frequently Asked Questions About Today's Cryptography, Version 4.1 [webpage] (2000); http://www.rsasecurity.com/rsalabs/faq/
Kahn, D. ``The Code Breakers.'' New York: Simon & Schuster Inc. (1996)
Schneier B. ``Applied Cryptography, Second Edition: Protocols, Algorthms, and Source Code in C'' Wiley Computer Publishing, John Wiley & Sons, Inc. (1996)
Program A O(n^2.2) - Program1
Program B O(n^2) - Program2
Program C O(n!) - Program4
Program D O(n^2*log n) - Program3
I recommend Program A (program1 in computing theory folder) to use as their "route" searching program, as program A
1. Compute the correct answer given valid data.
2. Perform the computation in a reasonable time.
| program | data | user + system | cost | program | data | user + system | cost | program | data | user + system | cost | program | data | user + system | cost |
| 1 | 3 | 0.04 | 22 | 2 | 3 | 0.02 | 22 | 3 | 3 | 0.17 | 22 | 4 | 3 | 0.18 | 22 |
| 1 | 4 | 0.03 | 19 | 2 | 4 | 0.01 | 23 | 3 | 4 | 0.17 | 23 | 4 | 4 | 0.18 | 19 |
| 1 | 5 | 0.08 | 22 | 2 | 5 | 0.02 | 22 | 3 | 5 | 0.18 | 22 | 4 | 5 | 0.17 | 22 |
| 1 | 6 | 0.11 | 32 | 2 | 6 | 0.01 | 34 | 3 | 6 | 0.17 | 37 | 4 | 6 | 0.18 | 32 |
| 1 | 7 | 0.12 | 28 | 2 | 7 | 0.02 | 32 | 3 | 7 | 0.17 | 32 | 4 | 7 | 0.24 | 28 |
| 1 | 8 | 0.03 | 21 | 2 | 8 | 0.03 | 27 | 3 | 8 | 0.17 | 34 | 4 | 8 | 0.4 | 21 |
| 1 | 9 | 0.11 | 19 | 2 | 9 | 0.01 | 19 | 3 | 9 | 0.19 | 30 | 4 | 9 | 2.2 | 19 |
| 1 | 10 | 0.09 | 27 | 2 | 10 | 0.01 | 39 | 3 | 10 | 0.18 | 42 | 4 | 10 | 22.01 | 27 |
| 1 | 20 | 0.24 | 34 | 2 | 20 | 0.01 | 45 | 3 | 11 | 0.17 | 48 | 4 | |||
| 1 | 30 | 1.23 | 43 | 2 | 30 | 0.02 | 60 | 3 | 12 | 0.2 | 52 | 4 | |||
| 1 | 40 | 1.26 | 45 | 2 | 40 | 0.03 | 67 | 3 | 13 | 0.18 | 39 | 4 | |||
| 1 | 50 | 6.12 | 53 | 2 | 50 | 0.02 | 70 | 3 | 14 | 0.18 | 63 | 4 | |||
| 1 | 100 | 1.216 | 100 | 2 | 60 | 0.02 | 83 | 3 | 15 | 0.18 | 55 | 4 | |||
| 1 | 200 | 8.4 | 200 | 2 | 100 | 0.04 | 125 | 3 | 20 | 0.17 | 73 | 4 | |||
| 1 | 300 | 19.04 | 300 | 2 | 200 | 0.07 | 223 | 3 | 30 | 0.19 | 113 | 4 | |||
| 1 | 400 | 33.38 | 400 | 2 | 300 | 0.12 | 317 | 3 | 40 | 0.21 | 155 | 4 | |||
| 1 | 500 | 51.04 | 500 | 2 | 400 | 0.23 | 432 | 3 | 50 | 0.21 | 223 | 4 | |||
| 1 | 2 | 500 | 0.27 | 522 | 3 | 100 | 0.31 | 488 | 4 | ||||||
| 1 | 2 | 3 | 200 | 0.52 | 1155 | 4 | |||||||||
| 1 | 2 | 3 | 300 | 2.71 | 1632 | 4 |
time it takes to execute 1 command in yallara as T;
(T is constant as we run all the programs in yallara.)
lets take p = total time program1 took to execute, f1(n) = operations required by program1 for a input of 'n'.
q = total time program2 took to execute, f2(n) = operations required by program2 for a input of 'n'.
r = total time program3 took to execute f3(n) = operations required by program3 for a input of 'n'.
s = total time program4 took to execute f4(n) = operations required by program4 for a input of 'n'.
there for
p = f1(n) * T ----(1) ==> f1(n) = p/T.
q = f2(n) * T ----(2) ==> f2(n) = q/T.
r = f3(n) * T ----(3) ==> f3(n) = r/T.
s = f4(n) * T ----(4) ==> f4(n) = s/T.
draw separate diagrams for f1(n), f2(n), f3(n) and f4(n), using 'n' as 'x' axis and 'p', 'q', 'r', 's' as 'y' axis. (diagrams are not provide as they are in gif format)
when we talk about increasing the computing power we are talking about reducing T (time it takes to execute one operation)
considering formula 1, 2, 3, 4 we can clearly see that even though the computing power increases by 1000 it only reduces the time a program takes to execute by 10^(-3).
for example if we assume that T is 0.1 for yallara
for a program of running time n! the time it takes to execute for n=50 is 3.04141 * 10^(64) ==>(9.6*10^(56) years)
but if we run the same program on a computer which is 1000 times faster then the time will be
3.04141 * 10^(61) ==>(9.6*10^(53)years) .
we have to atleast increase the computing power by 10^(56) to make this program finish the calculation within 24 hours!
... so is this really worth calculating?
what this proves us that no matter how fast the computing power increases but the best solution always depends on the algorithm.
We have been given the running time complexity of each program.
We should draw diagrams of those algorithms and compare them with the diagrams we draw above.
program4 = program C
* We could easily see, by comparing the diagram we draw for program 4 compares with the diagram we draw for program C( 'n!')
* looking at the running times of the programs, program 4 is the only program which has a very high growth of its running time as 'n' increases.
growth is very high, we cant even measure the running time for small n as n=11. And looking at the the document, program C is the program
which has a highest complexity .
there for i came to a conclusion as program4 is documented as program C.
*** note program4 uses exhaustive search which bound to give very precise cost for tour.
program 1 = program A
* Comparing the diagrams we have program 1-3 and program A,B&D we can see the diagrams are almost the same, which assures us that the
remaining programs are of almost the same complexity, as the programs documented (O(n^2.2), O(n^2), O(n^2*logn) ~= O(n^2)).
* Lin and Kernighan heuristic is the next best algorithm used in programs documented, there for comparing the costs we got for 'n' by using program
4 we can see the program 1 produces results as same as the program 4, which means that program 1 uses the Lin and Kernighan heuristic to find
the cost.
* Looking at the running time complexity of the given programs we could see that program A has the next highest complexity of O(n^2.2), and
looking at the growth of running time of the programs 1-3 we could see that running time of program 1 is higher then the other programs.
therefore i came to the conclusion as program1 is documented as program A
*** note program 1 calculates the costs identical to program4 which is bound to produce the optimal costs
program 2 = program B
* program B &-D uses greedy algorithms to fiend the costs for tours, program B use minimum spanning tree which has a complexity of O(n^2) while
program D use another greedy algorithm which has O(n^2*log n). among them program B has the lower running time complexity then program D.
Looking at the results we got we can see that program 2 has less rate of growth then the program 3 in running time as n increases.
* We cant compare the costs these algorithms fiend as these are greedy algorithms and they don't produce very accurate results.
there for i came to a conclusion as program 2 is documented as program B
remaining program
program 3 = program D
best solution for Hermes Logistics, specified range of 3 to
250 nodes.
Algorithms for solving this kind of problems are
divided into two classes: � Exact algorithms - The exact algorithms
are guaranteed to find the optimal solution in a bounded number of
steps. we can find exact solutions to small number of cities but as the
number of cities increases it becomes difficult to calculate as the
computing power require ment increase very rapidly. � Approximate (or heuristic) algorithms. -
In contrast, the approximate algorithms obtain good solutions
but do not guarantee that optimal solutions will be found. These
algorithms are usually very simple and have (relative) short running
times. Some of the algorithms give solutions that in average differs
only by a few percent from the optimal solution. Therefore, if a small
deviation from optimum can be accepted
Lets compare the different algorithms used in the programs, starting with
program B - this uses minimum spanning tree approximation algorithm which has a O(n^2) running time, use of this program is not encoraged as this algorithms doesn't guarantee that it'll fiend the optimum cost except for that it will fiend the cost which is less then the twice the amount of optimal cost. this could be modified to be within the factor of 1.5 of optimal but its much complicated.
program C - this uses exhaustive search which has a O(n!) running time, which require very large amount of computing power, there for this program is not recommended even though this produces the optimal results.
program D - this uses greedy heuristic which has a O(n^2 * log n) running time, this program is not recommended as this algorithms greedy as it tries to make the biggest jump towards the goal without thinking further ahead about what will happen from that point. in the average case having a good heuristic function could make greedy search much better, but there are some cases greedy doesn't work at all.
program A - this uses Lin and Kernighan heuristic algorithm which
has O(n^2.2) running time, The
Lin-Kernighan heuristic is generally considered to be one of the
most effective methods for generating optimal or near-optimal solutions
for this sort of problems. Lin and Kernighan�s algorithm was
reasonably effective. For problems with up to 50 cities, the
probability of obtaining optimal solutions in a single trial was close
to 100 percent. For problems with 100 cities the probability dropped to
between 20 and 30 percent. However, by running a few trials, each time
starting with a new random tour, the optimum for these problems could
be found with nearly 100 percent assurance.
by comparing the time these programs takes for n =300
(worst case scenario) program1 -19.04, program2 - 0.12, program3 -
0.21and program4 - cannot be calculated. we can see that most
accurate program takes longer time to calculate then the ones which are
not . for n =300 we cant calculate the time it takes to execute
program4 , the highest accurate algorithm. there for we cant use it.
The next accurate program is program1 which gives us accurate
solution and it only takes a reasonable time , there for we should use
program4.
these kind of problems compare to traveling sales man
problem and there is no proper solution for these kind of problems have
yet been found! there are various methods in the world but from
all the methods i know, modified Lin and Kernighan is the best
method .
Use program1 (Program A) when calculating the routes for 3 to 250 destinations.