Exercise 0.1 What does it mean that a function is effectively calculable? Which functions are effectively calculable? Give at least one example and illustrate which formal schema(s) define(s) it.
Exercise 0.2 Explain the relation between decidability of a predicate and the calculability of a function.
Exercise 0.3 Describe informally the operations that can be performed by a Turing Machine. Which functions can a Turing Machine emulate?
Exercise 0.4 Design the table of instructions for a Turing Machine that starts with a tape containing a block of 1s and it is otherwise blank. The machine is started scanning the leftmost 1, it goes through the input, it adds a 1 on the first empty cell on the tape right of the input, and it halts.
Exercise 0.5 Design the table of instructions for a Turing Machine that starts with a tape containing a block of n 1s, followed by a blank, followed by a block of m 1s. The machine is started scanning the leftmost 1 of the block of n 1s, and halts scanning the rightmost 1 of a block of (n + 1) + (m - 1) 1s and it halts.
Exercise 0.6 Write a Turing Machine program for the Tursi Simulator that adds a 1 to the end of a input of 1s.
Exercise 0.7 Write a Turing Machine program for the Tursi Simulator that implements unary subtraction.
Exercise 0.8 Write a Turing Machine program for either the Tursi Simulator or the Racket emulator which implements addition as follows:
- the symbols valid for this machines are (), 1, 0
- the input is of the form r(1s01s)
- the output is of the form r(1s), where the list of 1s is the sum of the first and the second block.
Exercise 0.9 Can you tell if the following program halts or not?
d e f f (int n )
i f( n > 0 )
f ( n-2)
elsif ( n > 0 )
f ( n+2)
end
end
Exercise 0.10 What does the Church-Turing thesis say? Comment on its significance for Computing.
Exercise 0.11 Choose one old technology for memory and explain its working.
Exercise 0.12 Describe the working of the von Neumann architecture through the simulation for an instance of the subtraction function.
Exercise 0.13 Which was the first business computer in the UK?
Exercise 0.14 What is Moore's Law?
Exercise 0.15 Offer a brief comparison of characteristics for object-oriented, functional and imperative programming styles.
Exercise 0.16 Present a OO-style program for inverting lists. Comment its structure.
Exercise 0.17 Present a functional style program for appending lists. Com- ment its structure.
Exercise 0.18 In which ways does CS differ from other science like Physics?
Exercise 0.19 Explain in brief what does a formal correctness proof for a pro- gram establish, for example in terms of pre- and post-conditions.
Exercise 0.20 Give at least one example of miscomputation, be precise about the LoA considered.
Exercise 0.21 Explain what the hypothetical-deductive method is.
Exercise 0.22 Describe the steps for building a good model for a computa- tional experiment.
Exercise 0.23 Choose one of the pre-defined models in NetLogo. Offer a brief explanation of its working and aims. Formulate an hypothesis related to the model. Offer a test-bed (at least 10 runs) under different conditions to test the hypothesis. Report on the findings.
Exercise 0.24 What type of simulations are used in science? For which pur- poses is each of them most fit?
Exercise 0.25 Present a NetLogo procedure that includes at least recursion, if-then and one loop. Explain what the procedure does.
Exercise 0.26 Explain in which way can simulation help formulate new knowl- edge or clarify known phenomena.
Exercise 0.27 Write a NetLogo model to do the following:
1.There is a maximal number of 1000 turtles
2.Turtles own a property like ‘having food'
3. There is a fixed amount of turtles with food: ask first just one turtle to have food, then more, like 3 or 5
4. The turtles move in some well-defined way: for example they move in squares or zig-zag or anyway else
5. When turtles cross each other they pass food
Check that every turtle gets food. Is it faster or slower if a smaller amount of turtles have food at the beginning?
Exercise 0.28 Explain the difference between isomorphic, analogical and sim- ilarity relation between real-world and simulated properties.
Exercise 0.29 Write a NetLogo model to do the following:
1.There is a maximal number of 1000 turtles
2.Turtles own either a property like ‘having food' or one like ‘having water'
3.There is a fixed amount of turtles with food and a fixed with water
4.The turtles move in some well-defined way: for example they move in squares or zig-zag or anyway else
5.When turtles cross each other they pass food under the following conditions: if a turtle who has food crosses one without either food or water, it gives food; if a turtle who has food crosses one without food but with water, it gives food and receives water; if a turtle who has food crosses one with food and water, nothing happens; the same rules apply for tur- tles with water; a turtle with food and water changes to a pre-defined colour.
Check that every turtle gets food and water.
Exercise 0.30 Recall the definition of Graph. What is the difference between total, random and scale-free graphs?