COMP2022: Formal Languages and Logic
2017, Semester 1, Week 13
Joseph Godbehere June 6, 2017
COMMONWEALTH OF AUSTRALIA Copyright Regulations 1969 WARNING
This material has been reproduced and communicated to you by or on behalf of the University of Sydney pursuant to part VB of the Copyright Act 1968 (the Act).
The material in this communication may be subject to copyright under the Act. Any further copying or communication of this material by you may be subject of copyright protect under the Act.
Do not remove this notice.
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Outline
▶ Proof of undecidability of the Halting problem
▶ Assignment 3 results (best proofs!)
▶ Exam advice ▶ Topics
▶ Structure ▶ etc.
▶ Revision
3/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Proving the Halting Problem is undecidable
Suppose the Halting problem is decidable.
Then there exists some universal Turing machine H such that H(a,b) accepts if and only if the TM represented by a would halt on input b.
The language L of H is:
{a, b | a represents a TM, b is an input string, a halts on b}
4/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Proving the Halting Problem is undecidable
H (a, b) accepts iff TM a halts on input b
Let X(c) be a Turing machine which either:
▶ If H (c, c) accepts, then loop forever
▶ If H (c, c) rejects, then halt
5/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Proving the Halting Problem is undecidable
Now consider what happens if we use “X , X ” as input to H . i.e. what does X do when given its own representation as input.
6/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Proving the Halting Problem is undecidable
Now consider what happens if we use “X , X ” as input to H . i.e. what does X do when given its own representation as input.
Case 1: If H(X,X) accepts, then X must halt on input X, because H is a solution to the Halting problem. However, X will loop forever because H (X , X ) accepts.
6/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Proving the Halting Problem is undecidable
Now consider what happens if we use “X , X ” as input to H . i.e. what does X do when given its own representation as input.
Case 1: If H(X,X) accepts, then X must halt on input X, because H is a solution to the Halting problem. However, X will loop forever because H (X , X ) accepts.
Case 2: If H(X,X) rejects, then X cannot halt on input X, because H is a solution to the Halting problem. However, X will halt because H (X , X ) rejected.
6/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Proving the Halting Problem is undecidable
Now consider what happens if we use “X , X ” as input to H . i.e. what does X do when given its own representation as input.
Case 1: If H(X,X) accepts, then X must halt on input X, because H is a solution to the Halting problem. However, X will loop forever because H (X , X ) accepts.
Case 2: If H(X,X) rejects, then X cannot halt on input X, because H is a solution to the Halting problem. However, X will halt because H (X , X ) rejected.
Both cases lead to contradictions, so the assumption was incorrect. i.e. The Halting problem cannot be decidable.
6/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Statistics
attempts
proofs
lines
errors
Q1
493
173
6007
4540
Q2
237
173
1356
1474
Q3
403
178
2569
1969
Q4
271
152
4182
2266
Most persistent student submitted over 800 lines
7/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Most painful inference rule
Disjunctive Syllogism (DS)
(A∨B), ¬A B
▶ 1400 errors, 603 correct uses
8/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Loneliest inference rule
Constructive Dilemma (CD)
((A→B)∧(C →D)), (A∨C) (B ∨ D)
▶ Used correctly only 11 times
9/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Shortest proof: Q1
First to find a proof this short was zzha4377 (+ 14 others)
P. L. 1 1 2 2 2 3 2 4 2 5 2 6 2 7 2 8 2 9 2 10 1, 2 11 2 12 2 13 1, 2 14 1, 2 15 1 16
Formula
A
¬¬(B↔(A∧¬B))
(B↔(A∧¬B))
((B → (A∧¬B))∧((A∧¬B) → B)) (B→(A∧¬B))
(¬B∨(A∧¬B))
((¬B ∨A)∧(¬B ∨¬B))
((¬B ∨¬B)∧(¬B ∨A))
(¬B∨¬B)
¬B
(A∧¬B)
(((A∧¬B) → B)∧(B → (A∧¬B))) ((A∧¬B)→B)
B
(B∧¬B)
¬(B↔(A∧¬B))
Justification Premise
Premise
Double Negation Equivalence Simplification
Def. of Implication Distribution Commutation Simplification Idempotence Conjunction Commutation Simplification Modus Ponens Conjunction Indirect Proof
Refs
2
3
4
5
6
7
8
9
1, 10 4
12
11, 13 10, 14 2, 15
10/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Shortest proof: Q2
First to find a proof this short was lili5475 (+ 69 others)
P. L. Formula
1 1 A
2 2 ((A∧¬B)→B) 2 3 (A→(¬B→B)) 1, 2 4 (¬B→B)
1, 2 5 (¬¬B∨B)
1, 2 6 (B∨B)
1, 2 7 B
Justification Premise
Premise Exportation Modus Ponens Def. of Implication Double Negation Idempotence
Refs
2
1, 3 4
5
6
11/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Shortest proof: Q3
First to find a proof this short was lili5475 (+ 55 others)
P. L. Formula
1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8
Justification Premise
Double Negation Addition DeMorgan’s Laws Conjunction DeMorgan’s Laws Def. of Implication Commutation
Refs
1
2
3
2, 4 5
6 7
B
¬¬B
(¬¬B ∨
¬(¬B ∧
(¬¬B ∧
¬(¬B ∨ ¬(B→(¬B∧A)) ¬(B→(A∧¬B))
¬A)
A)
¬(¬B ∧ A)) (¬B ∧ A))
12/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Shortest proof: Q4
First to find a proof this short was kste4439 (+ 3 others)
P. L.
1 1
2 2
2 3 2 4 2 5 2 6 2 7 1, 2 8 1, 2 9 1, 2 10 1, 2 11 1, 2 12
Formula
A
(B→(A∧¬B)) (¬B∨(A∧¬B))
((¬B ∨A)∧(¬B ∨¬B)) ((¬B∨A)∧¬B) (¬B∧(¬B∨A))
¬B
(A∧¬B) ((A∧¬B)∧¬B)
(¬¬(A ∧ ¬B) ∧ ¬B) ¬(¬(A∧¬B)∨B) ¬((A∧¬B)→B)
Justification Premise
Premise
Def. of Implication Distribution Idempotence Commutation Simplification Conjunction Conjunction Double Negation DeMorgan’s Laws Def. of Implication Conditional Proof Def. of Implication DeMorgan’s Laws Equivalence
Refs
2
3
4
5
6
1, 7 7, 8 9
10 11
2, 12 13 14 15
1 1 1 1
13 ((B → (A∧¬B)) → ¬((A∧¬B) → B))
14 (¬(B → (A∧¬B))∨¬((A∧¬B) → B))
15 ¬((B → (A∧¬B))∧((A∧¬B) → B))
16 ¬(B↔(A∧¬B))
13/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Exam Notes
You are allowed to bring a single sheet of A4 paper containing your own notes (printed or written, on both sides.)
The tables of Equivalence Laws and Inference Rules for propositional and predicate logic will be provided to you with the exam paper (the exact same sheet you can download on Ed.)
14/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Exam structure
There are some short answer questions testing general knowledge of the course.
Most of the exam consists of practical questions, applying the methods we’ve used in tutorials and assignments (for example, minimising a DFA)
15/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Possible exam topics
16/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Possible exam topics
Weeks 1 to 12
16/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Regular languages
▶ DFA
▶ NFA
▶ Regular expressions
▶ Transformations between representations
▶ Minimal DFA
▶ Prove that a language is regular by giving a DFA, NFA, or Regular Expression
▶ Prove that a language is not regular by using the Pumping Lemma to find a contradiction
17/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Context-Free languages
▶ Context-Free Grammars
▶ Push Down Automata (PDA)
▶ LL(1) grammars
▶ Identifying non-LL(1) grammars
▶ Finding equivalent LL(1) grammars
▶ FIRST and FOLLOW sets
▶ Building parse tables
▶ Chomsky Normal Form
18/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Propositional Logic
▶ Translating arguments from English into Propositional Logic
▶ Proofs in the Natural Deduction System
▶ Equivalence Laws
▶ Inference Rules ▶ Proof by Resolution
▶ Conjunctive Normal Form
▶ Resolution Rule (+ Indirect Proof)
▶ Proving logical tautologies
▶ NDS proof
▶ Quine’s method
19/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Predicate Logic
▶ Translating arguments from English into Predicate Logic
▶ Proofs in the Natural Deduction System ▶ Equivalence Laws
▶ Plus laws involving quantifiers ▶ Inference Rules
▶ Plus rules involving quantifiers
▶ Proving if a formula is valid (or invalid) ▶ Prenex Conjunctive Normal Form
20/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Turing Machines
▶ Turing Machines
▶ Designing a TM to solve a problem
▶ Concepts and examples of: ▶ Computability
▶ Decidability
▶ (In)tractability
21/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Time management
▶ There are a lot of topics!
▶ Rule of thumb: number of marks = number of minutes
▶ The 2 hour exam has 100 marks total
▶ Don’t know how to proceed with a question?
▶ Skip it!
▶ Do questions you are confident on first
▶ Then go back to the harder questions
22/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Working
▶ Show your working
▶ An incorrect answer without working will get zero
▶ An incorrect answer with working might get partial marks
▶ Some questions require you to show your working
▶ i.e. you cannot get full marks without showing how you reached the solution
23/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Revision sessions
When:
▶ Tuesday afternoon?
▶ Thursday afternoon?
▶ Exact times will be announced on Ed later this week
Where:
▶ SIT Lecture Theatre 123
What:
▶ There will be no specific content. ▶ Just come with questions.
24/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
Links to other units
▶ all IT courses, in particular:
▶ COMP2007/2907: Algorithms and Complexity
▶ COMP3308/3608: Introduction to AI
▶ COMP3109: Programming Languages and Paradigms
▶ MATH3066: Algebra and Logic
▶ Very interesting mathematics course. Explores predicate logic
and Turing machines more rigourously than we did this semester.
▶ PHIL2650: Logic and Computation
25/26
Turing Machines Assignment 3 Exam topics Exam tips Revision sessions What next?
That’s it!
Thanks for the fun semester.
Don’t forget to complete the Unit of Study Survey:
http://sydney.edu.au/itl/surveys/complete/
26/26