Evaluation criteria

The default is that all who have really tried to solve the problem get 2 points. If you have solved the whole problem and learnt also some general method and analyzed it, you get 3 points. If the report is just a sketch (e.g. you haven't answered all questions) it is 1 point (or even 0 point, if there is no trial at all). To get 3 points the report should contain:

In problem 0

- some solution to code special characters, e.g. their ascii numbers or new user defined Morse codes
- recognition that binary codes are just binary numbers and Morse alphabet is based on binary signals
- all symbolic (written) languages can be coded by Morse alphabet (binary alphabet) <-> such languages can be managed by the digital computer
- also good point: coding in binary alphabet increases the length of the message enormously: if we have to code n characters, each character needs log n bits (2-based logarithm <- with k bits you can code 2^k different strings of equal length)

In problem 1

- recognition that there are (uncountable number of) problems which are totally unsolvable
- some problems which are so time consuming that they are unsolvable in practice
- we have to describe the problems in some formal way to be able to compare and analyze them (it's not sensible to try to really solve them for that)
- some trial to classify problems by their difficultiness, e.g. reductions to known problems (database of "prototype problems" of different levels) or reference to Chomsky hierarchy Also good points:
- Chomsky hierarcy gives some outlines, how "difficult" the problem is, and we can use reductions to known problems in some classes (or outside classes to show that something is unsolvable)
- time and space requirements can also be studied by reductions to some problems in a known requirement class (e.g. NP-complete problems)
- some problems are compuational by their nature ("humanistic" problems)
- for some problems there may exist only approximative solutions
- sometimes division into subproblems helps: if a subproblem is unsolvable, the whole problem is as well

Problem 2

- some solution for both problems (address and phone number) with regular expressions (or other exact notation, which is capable of describing the patterns)
- analysis of the performance -> in practice we will need some further heuristics or human work. - There is no perfect solution for problem like sending MIU-journal to all potential orderers - a computer program cannot understand the meaning of text! - same method works with all pattern matching problems
Also good point: if we allow arbitrary number of paranthesis in the definition, the regular expressions can't describe them!
- using only database searches is enormously unefficient, and we cannot expect such databases. If we have such databases, we can use them to verify promising patterns.

Problem 3

- transition diagram, which describes the functions of the coffee machine, without any further restrictions (the notation of finite automata was not demanded, if your own notation caught the same)
- pseudocode algorithm, which descibes the functions - simplest way is a loop with switch statement as given in the lecture material

Problem 4

- basic idea:
1) construct automata from the students' solutions
2) minimize the automata: the result of minimization is unique
3) compare the automata with the solution automaton (you can first check that it is minimal - it was)
- Important point: how the automaton is constructed from the given regular expression?

Problem 5

1) Without quotation marks the rhyme language is regular. Let's denote:
t=The story begun
Now we can give a regular expression (t:)^* t (at least once the sentence, but can be repeated as many times as wanted)
2) With quotation marks nonregular: the problem is that we should have equal number of beginning quotation marks and end quotation marks, and finite automata cannot count them.

(t:'')^k t ('')^k

So in fact of form a^k t b^k, which looks very familiar... Everybody who even tried to solve the nonregularity with the Pumping Lemma got 3 points.

Problem 6

- Everybody, who returned a report with idea description and a correct grammar and represented the masterpiece in the Art Exhibition got 6 points.
- If the idea report was returned with a proper grammar, but not implemented, it was 2 points.

Problem 7

A pushdown automaton (represented as a diagram or transition table) was required. N.B. You need different stack symbols for each parantheses type.

How to program: you can use a stack as in the automaton (i.e. push a parantheses/special character into stack, when you meet a beginning paranthesis, and pop a character, when you meet an end parantheses. Compare if they correspond each other.

Problem 8

The grammar was most important, so if you had a correct grammar and even some idea how to make a recursive parser, we gave 2 points. If the parser was at least nearly correct, you got 3 points. For parser you had to transform the grammar to LL(1) (or LL(k) for some k, if you read words instead of characters) form. Considerations about LL(1)-transformation could compensate other errors.

Problem 9

For 3 points:
- general idea of three tape summing machine (not only for some example strings): either as transition diagram, transition table or very careful description by words (also described, what to do, when end symbol is met)
* carry bit can be remembered by moving to some state or
* it can be written into third tape and summed with new digits of operand strings
- if just the transitions, then the idea also described by words or simulated by examples
- answer to question, can it be performed by 1-tape machine (if it was described carefully, it could compensate minor faults)
- if only the idea by words or by simulating the tape with example strings, then 2 points, if correct

Problem 10

The idea is to model the properties of programs with Turing machines and study, if they are solvable.
* program size is <=K kB <-> The code of Turing machine M, length(C_M) is <=K. This can be easily checked.
* Does the program take more than 5 minutes with input x? <-> Does Turing machine M perform more than K transitions with input x? We can use universal machine and simulate M for at most K transitions. But: the simulations takes itself more than 5 transitions. In fact we can prove, that we cannot check it in shorter time.
* Does program need more than K kB with input x/any input? <-> Does TM M use more than K cells of working tape with input x/any input? Again we can simulate M with universal machine, but if M never halts, we don't find the answer. So partially unsolvable.
* Does the program contain a dangerous virus? <-> There are several ways to model this. E.g. does TM M eneter a virus-state q_virus? Or does it write on some reserved area (between tape cells i and j)? Or does its code contain some other TM's code? This is partially solvable, as the previous one.
* Does the program crash? <-> Does the TM M enter crash-state q_crash? (Or division by 0 can be modelled by writing 0 to cell i. Writing outside legal memory area can be modelled by writing outside j:th cell of working tape.) Partially solvable, as the previous one.
* Does the program work correctly? <-> If we have a TM M which works correctly and we want to verify that also M' work correctly, we should check that L(M)=L(M'). This is totally unsolvable problem, when the language is infinite. One criterion for correct work is halting, and we know it is already unsolvable property.

Important notes:
- TM's can be coded and the code checked or "run"
- with the universal machine you can simulate other TM's and check if they have some property
- if M doesn't halt, then the universal machine doesn't halt either
- This is only an intuitive reason for unsolvability, but proofs were not required.

The most important was to invent the way, how to study these properties (model them by Turing machines). Minor errors were accepted, if the idea was correct. If you had correct answers and they were well justified without Turing machines (e.g. contradiction proof for hypotethical programs), it gave also 3 p. You could also justify your answer by recognizion that semantic properties are generally unsolvable.