COMPUT ING T HEORY
COSC1107/1105: A Computable Odyssey Course Material
Semester 2, 2020
Cryptography
Copyright By PowCoder代写 加微信 powcoder
Complexity
The persons mainly responsible for assembling this material are and .
However, there are a number of people who have contributed to the preparation of this material, including , , , , , , , , , , Lavindra de Silva, , , Lai, , , and .
Since 2012, this notes uses tikz LaTex drawing package (www.texample.net/tikz/). Please send any corrections or comments to .
Last Edited: Tuesday 3rd August, 2021 14:41
Table of Contents
InitialQuestions………………………………. ii Introduction………………………………… iii Tutorials………………………………….. vii BackgroundMaterial ……………………………. viii RandomNumberGeneration ………………………… x
Lecture Notes 1 Section1:Complexity …………………………… 1 Section2:Cryptography ………………………….. 5 Section3:GrammarsandParsing………………………. 9 Section4:FiniteStateMachines ………………………. 23 Section5:TuringMachines…………………………. 32 Section6:Computability ………………………….. 45 Section7:Complexity(revisited)………………………. 51 Section8:Cryptography(revisited)……………………… 58 Section9:Grammars(revisited) ………………………. 61 Section10:Automata(revisited) ………………………. 64 Section11:ChomskyHierarchy ………………………. 74 Section12:Extensiontopics ………………………… 79 TilesRevisited……………………………….. 83 AndFinally………………………………….. 83
Some Initial Questions
Below are three problems, all to do with tiles, which will hopefully set the scene for this subject. How would you go about attacking these problems?
Tiling Problem 1:
Given a set of tile designs T , is it possible to cover any rectangular area using only designs from T ? Rotations are not allowed, and the patterns on each of the four sides of a tile must match the neighbouring tiles.
Informally, can we tile any bathroom this way? (including some enormous examples as the bathrooms at Versailles, or the , or …)
Tiling Problem 2:
Given a set of tile designs T and a bathroom wall of size s × t, is it possible to cover the wall using only designs from T ? Rotations are not allowed, and the patterns on each of the four sides of a tile must match the neighbouring tiles.
Informally, can we tile my bathroom this way? This is clearly a more specific question that the earlier version.
Tiling Problem 3:
Given a set of tile designs T and a bathroom wall of size s × t, is it possible to cover the wall using only designs from T ? Rotations are allowed, but the patterns on each of the four sides of a tile must still match the neighbouring tiles.
Informally, can we tile my bathroom by turning the tiles around, if necessary?
Introduction
There are a number of topics, but there are five main ones: • Complexity.
• Cryptography.1 • Grammars.
• Automata.
• Computability.
Complexity is concerned with measuring the cost of computations. There are many possible aspects to this; however, we concentrate on maximum execution time. Even then, it is not hard to find problems which cannot be solved in any reasonable time, no matter how fast hardware improves.
Cryptography is concerned with encrypting information so that no unauthorised person can read it. The main technical issue is how we can be sure of this; the answer is to rely on problems which no-one can solve in any reasonable time.
Grammars are concerned with the specifications of syntax rules — in particular, how do you indicate to a machine what programming language constructs are legal and which are not? Automata are concerned with the modelling of computation, and in particular how we can reason about computation. In particualr, the key role of memory is emphasised in three dif- ferent approaches to memory, being none (finite state machines), a single stack (a pushdown
automaton) and a semi-infinite tape (a Turing machine).
Computability is concerned with the fundamental limits of computation (in contrast with the
resources view used in complexity). In particular, it may be surprising to learn that there are some problems for which it can be proved that computers (at least in their current conception) cannot solve.
As may be noticed, there is an inter-dependence between these topics.
Also, observe that the order of the topics in this course notes may not correspond to the order delivered during the weeks. However, it should be straightforward to find the relevant section for each week.
1No longer covered in the course.
Cryptography
Complexity
Computability
This picture depicts the general topics touched during the course. Notice, however, that in the current course we do NOT include Cryptography. Nonetheless, the section on Cryptog- raphy was left in the course notes for interest of the reader and as an example of when difficult computational problems are very useful.
We will mostly use a sequence compatible with several textbooks, starting with Automata and finishing with Complexity.
Specific Skills Covered
• analyze algorithmic complexity • read and write automata
• NFA → DFA conversion
• read and write grammars
• parsing and derivations
• decidability
• tractability and O(n) notation
• intractability and NP-completeness • grammar and language classes
• automata relationships
• grammar relationships
Motivating Questions
• How can we reason about programs?
• What is possible and impossible?
• How can we tell the difference?
• How do we show that some things are impossible?
• Can we ever say “Never”? “Always”?
(e.g. How do we reason about cryptographic attacks?)
• What precisely are programs anyway?
• How can we be precise about complexity costs?
“Put the right kind of software into a computer, and it will do whatever you want it to. There may be limits on what you can do with the machines them-
selves, but there are no limits on what you can do with software.” April, 1984.
• What limits are there to computation? • How do we establish them?
• Can we do anything about such limits? • What is an algorithm?
• Do algorithms always exist?
• What can and cannot be computed? • What can be feasibly computed?
We can establish claims about “exists”, “sometimes”, “possible”, etc. by construction, such as “there is at least one bearded lecturer at RMIT”.
It is generally harder to establish claims about “all”, “always”, “impossible”, etc., such as “Humans will never reach the moon”.
“Never” is a very long word! Or, as Treebeard the Ent puts it “Never is too long a word, even for me”. 2
Overview Problem
The problem described below is intended as an overview of the material studied in this subject. You are not required to provide a solution to it; it is intended as a means of showing how the material fits into the “big picture”. In particular, you will not be required to know any of the details of quantum computing.
Problem Statement
You are employed as an IT professional at a company called Incandescent Technolo- gies. One day your boss comes into your office and says: “I hear that there is a new kind of computer called a quantum computer, which can apparently perform some computations much faster than those we have now. No such machines are currently commercially available, but we need to be prepared for the possibility that they will be in the near future. I want you to investigate this topic and prepare a comprehensive report on it, specifically addressing the points below:
1. Will the security of our systems be affected? Could some hacker utilise a quan- tum computer to break into our systems?
2. Can we harness the power of quantum computers to make our compilers run faster?
3. Are the benefits of quantum computing limited to faster processing alone? Or can we now solve problems which were unsolvable before?
Please, have your report on my desk by the end of the semester.”
2J.R.R. Tolkien, ‘The Lord of the Rings’, p.1016, Harper-Collins, 1991.
Addressing this problem
In order to tackle this problem (which is (deliberately 🙂 very broad), you may find the following questions useful.
1. (a) How do modern-day cryptographic systems work?
(b) What relationship is there between high complexity problems and cryptography? (c) How are factorisation and an algorithm for finding primes linked to cryptography? (d) How do we estimate the execution time of a program?
(e) What are intractable problems and why are they important?
(f) How much faster hardware do we need to solve problems with exponential com- plexity?
(g) What approaches can we use to deal with difficult problems?
(h) What are NP-complete problems and why are they important?
2. (a) How does parsing work?
(b) What are grammars used for?
(c) What are some different classes of grammars and how do they differ? (d) What can regular expressions express?
(e) What are finite state machines and how do they work?
(f) what are the differences between deterministic and non-deterministic finite state automata?
(g) What are pushdown automata and how do they work?
(h) What are turing machines and how do they work?
3. (a) Can we always find an algorithm to solve a problem?
(b) What are the relationships between different machines and grammars?
(c) WhatformalmodelsofcomputationaretherewhicharemorepowerfulthanTuring
(d) What is the most powerful kind of Turing machine?
(e) Can we show without any doubt whether all problems could or couldn’t be solved
by computers? How?
Questions such as these will be discussed at lectures and answered by the problems set for
each week of tutorials.
Whereas lectures are meant to give the “big picture” of each aspect of the course, tutorials are meant to deal with the actual technical details. Both lectures and tutorials are important, but tutorials are more personal, and a tutor will expect students to attend them unless there is a very good reason not to. It is extremely difficult, if not impossible, to get the technical training required for passing the course without attending tutorials.
During tutorials you will be working in learning groups of around 2-4 people. Your tutor will spend time with each group, assisting as necessary to ensure that you are on the right track. You should discuss and work actively together to ensure that everyone fully understands the subject material. In some tutorials you will have specific exercises to do — these are designed to assist you in mastering the various skills and concepts. Tutorial time can also be spent discussing assignments as well as material from lectures or the textbook. In the last part of each tutorial, tutors will go over some questions of the previous tutorial in the whiteboard, so make sure to attend and stay around until the end!
During each week you should:
• Attendlecturestogetthegeneralbigpictureofthematerial.Sometimeslecturesprovide
essential core information not covered in tutorials.
• Attend tutorials to dive into the technical details and get the necessary training.
• Aftertutorials,completebyyourselftheremainingquestionsthatwereleftincomplete
in the tutorial. You may want to collaborate with other fellow students. However, you are meant to develop yourself the solutions. Just knowing the solution (e.g., because another student explained it to us) means very little. Indeed, a moderate form of collaboration is encouraged as a useful part of any educational process. Nevertheless, students are expected to do their own thinking and writing. Never copy another student’s work, even if the other student “explains it to you first.” Never give your written work to others. Do not work together to form a collective solution, from which the members of the group copy out the final solution. Rather, walk away and recreate your own solution later.
• Usetheonlineforumtohelpcompleteeachtutorialaswellasclarifyingaspectscovered in the lecture that you have not fully grasped.
• Ask yourself: would I be able to solve similar exercise completely by myself?
After each week’s tutorial, it is a very good idea to write out the complete solutions to the problems set that week, particularly as for some tutorials your group may not complete all the problems in class. This will help you gather the content of the course up to the necessary details. This means that you can commence the following week’s class with a brief discussion of the solutions, possibly by asking your tutor for feedback on your written work. Such regular clarification of your own understanding of the topic is the best form of preparation for the final
Background Material
The material in this section is not examinable. However, you should make yourself familiar with this material, and it will be useful for reference.
Mathematical Formalism
To answer such questions, we use mathematical formalisms to describe computation.
• We can reason about the program and its behaviour.
• We can estimate the cost of the program.
• We can be rigorous and precise.
• We can (sometimes) establish “negative” results, e.g. “There is no algorithm to solve problem X”.
• For this subject, mathematics is generally “read-only”.
Mathematical Language
Definition A precise mathematical statement of what we mean, such as “A prime number is a positive integer which has no factors other than itself and 1”.
Theorem/Proposition Apropertywhichwecanshowalwaysholdsandisinterestingbyitself, such as “All even numbers except 2 are not prime” or “There are an infinite number of primes”.
property that always holds and that is used as a stepping stone to a larger result rather than as a statement of interest by itself.
Corollary A property that always holds and is interesting by itself, but that can be readily deduced from another result, generally a Theorem or Proposition.
Proof The justification for our statement. This must cover all cases and leave no room for doubt. Techniques used here include proof by induction and proof by contradiction.
Mathematical Methodology
We will often use mathematical methods to state precise results, usually in the form of a theo- rem and a proof. This requires us to
• write a precise summary,
• provide guaranteed behaviour (proof), • concentrate on important parts,
• prove it can be applied elsewhere.
Two common techniques used for proofs are proof by induction and proof by contradiction.
Mathematical Induction
Let P be a property defined on N. How can we show that ∀x ∈ N, P(x) is true? A generally applicable method is the principle of mathematical induction. If
1. P(0)istrue,and
2. if P(n) is true, then P(n + 1) is true.
Then by the principle of mathematical induction, ∀x ∈ N, P (x) is true. Note that step 2 is an abbreviation of
P(0) ⇒ P(1) P(1) ⇒ P(2) P(2) ⇒ P(3) …
Proof by Contradiction
To prove a statement P , it is sometimes easier to assume its opposite, written as ¬P , and derive a contradiction.
Key Idea: if ¬P cannot hold, then P must be true.
Step 1 Assume ¬P is true.
Step 2 Based on this assumption draw a number of conclusions. Step 3 Establish that the conclusions lead to a contradiction. Step 4 Therefore ¬P cannot be true (as was assumed).
Step 5 Therefore P is true.
Limits of Computation
Hardware speeds currently tend to double every two years (Moore’s Law). “Computers can do anything!”
• Some problems cannot be solved even in principle (i.e. given unlimited resources)
• Some problems are too difficult to be solved in practice (i.e. the needed resources are too
• Some problems are too difficult to solve on a given hardware platform.
Some Example Problems
You may like to consider which category these problems fall into:
Write a program which finds the cheapest route to visit a given list of cities. Assume you have a list of all cities and the cost of flying between each two cities. The program should take as input a start point and a list of cities to visit. Write a program which determines whether another program terminates on all possible inputs (i.e. is there an input that puts the program into an infinite loop?).
Write a program to index and make available all full text articles from the last 10 years of The Age newspaper.
Random Number Generation
A nice example of the need to think things through before coding is that of random number generation. A sequence of seemingly random numbers has many applications.
• Simulation
• Program testing
• Numerical analysis
• Decision making and scheduling • Games ( )
Many of these problems can be mapped into the problem of generating a random sequence of integers between 0 and a given number M .
• Random 10 letter words: sequences of length 10 between 0 and 25. 0 becomes ‘a’, 1 becomes ‘b’ etc. (n − 1 becomes nth letter of alphabet).
• Random arrival times, a sequence of real numbers in the interval [1, 10): for 0 ≤ X < M , useY =1+9(X/M).
• Random words from a dictionary: if there are N items in the dictionary, use the nth word, where n = ⌈1 + N(X/M)⌉.
Problem: To generate a sequence of seemingly random integers between 0 and M from a computer program.
23, 654, 1, 54, 777, 233, 4232, . . . 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, . . . Non-examples:
1, 2, 3, 4, 5, . . .
1, 4, 9, 16, 25, 36, . . .
“Spaghetti attempt”
This was an attempt by to write a program tha was as unpredictable as possible, and hence would (hopefully) produce a sequence of random numbers.
Input: A 10-digit number X
Output: Next number in the sequence
K1 Y ← ⌊X/109⌋
K2 Z ← ⌊X/108⌋ mod 10. Goto Step K(Z + 3)
K3 If X < 5 × 109 then X ← X + (5 × 109)
K4 X ← ⌊X2/105⌋ mod 1010
K5 X ← (1001001001 × X) mod 1010
K6 If X < 108 then X ← X + 9814055677, else X ← 1010 − X K7 Swap the lower 5 digits of X with the higher 5 digits
K8 Same as K5
K9 Decrease each non-zero digit of X by one
K10 If X < 105 then X ← X2 + 99999, else X ← X − 99999 K11 IfX<109 thenX←10×X.GotoK11
K12 X ← ⌊X(X − 1)/105⌋ mod 1010
K13 IfY >0thenY ←Y −1;GotoK2
The hope was that starting with a number such as 1234567890 and repeatedly applying this algorithm would produce a random sequence of numbers. Unfortunately, what came out was a sequence that soon just repeatedly produced the number 6065038420 — not very random at all!
Moral (Knuth): Random numbers should not be generated with a method chosen at ran- dom. Some theory should be used.
Desirable properties of a random sequence:
• each integer 0, 1, . . . M − 1 occurs equally often,
• each pair, triple, etc. occurs consecutively equally often,
• the sequence should have mean (M − 1)/2 and variance M2/12, and • successive numbers should be independent.
Linear congruential generator
One method to do this is to use a linear congruential generator.
Xn+1 =(a∗Xn +c)modM,wherea,c≤M and0≤Xn
seed = random(seed);
printf(“%d\n”, seed);
int random(int seed) {
return(((25173*seed + 13849) % 65535));
Generated Numbers:
7564, 43246, 43522, 44560, 25669, 4486, 23122, 47620, 51424, 62881, 50407, 20590, 9604, 16726, 60607, 19060, 29494, 20296, 14197, 32575, 50404, 10606, 9097, 33340, 40459, 8821, 32302, 59350, 30004, 13666, 34852, 26200, 2209, 47326, 56017, 13195, 40204, 12136, 54742, 29770, 21334, 60841, 11392, 3505, 35104, 12901, 44797, 27985, 44539
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com