M381 Number theory and logic First TMA

It’s been a while since my last post for which apologies. I have just sent off what I have managed to complete, for the first TMA for M381, Number theory and logic. Daniel and Duncan on their blogs have given a good overview of the topics so far and also the fact that at this level one is expected to think for one self a lot more. Duncan is way ahead as usual but then he did start early last year whilst I was busy on Fluids, Music and Quantum Mechanics. I started looking at the units about 5 weeks ago and  I have just about completed the units for TMA01, two number theory units and an introductory one on computability. Not much to add to what Duncan and Daniel have already said although I do find it strange that the course has decided to put computablity ahead of logic, a relatively gentle break in, would have been to tackle at least the basic elements of logic first, truth tables etc which most people are probabily aware of, before embarking on what is quite a challenging introduction to computability.
Again rather than introduce computability via Turing machines, the course has decided to use URM (Unlimited Register Machines) which were introduced in the 1960’s I think. As Duncan has pointed out URM machines are based around four simple commands
        Z(n) make the contents of the given register zero
        C(n,m) copy the contents of register n to m (Not the other way around which it is very easy to confuse)
        S(n) increment the contents of register n by 1
        J(m,n,q) jump to instruction q if the contents of register m are the same as register n.
URM machines are meant to simulate computer programming, but as a caveat I would add that the Jump instruction seems very similar to the now frowned upon GOTO statement, that has lead to piles and piles of spaghetti code and provides quite a great deal of diificulty in interpreting a URM code. Still it can be useful in providing loops until two registers are made equal simply by including an instruction of the form J(n,n,q) where q is a command earlier in the list. I dare say however a new formulation of computability, reflecting current programming practice, could be devised.

Anyway onto the TMA, it fell into two parts 6 questions on Number theory and 4 questions on computability
Question 1 A relatively straightforward one on the Eulidean Algorithm familiar from the last part of MS221

Question 2 A question on induction which had actually changed from the initial one, a bit tricky, but once one had seen how to proceed it was relatively straightforward

Question 3. A question on proving  a condition on the last three digits of any number  to be satisfied if the number that is to be divisible by 8. This was quite tricky at first but once you realised what was going on it became obvious. This question is really clever, the sort of thing that doesn’t involve any complicated maths, but requires some thought. I hope there are more questions like this as the course proceeds

Question 4. Another question on divisibility involving factorials divided into three parts first calculating the possible remainders of n^2 when expressed as 1Ok+r, Then proving what factorials are divisible by 10. Finally putting parts one and two together to find out what factorials can be expressed as squares Think I got most of this out.

Question 5 was on Fibonacci Numbers and as I hadn’t had time to look at this topic in any great detail I left it

Question 6 was a question on showing that there are infiinitely many primes of a certain form. As this was very similar to a theorem in the unit it didn’t require that much adaptation to generate a similar proof.

So Apart from question 5 feel reasonably confident that I have got most of this correct.

Second Part Computability part 1
Question 7 Asked us to demonstrate what would happen to a given URM program draw a flow diagram and work out what the code was trying to do. I think I got it out but it would have been easier if one of the copy instructions had their registers swapped ie C(n,m) instead of C(m,n) not sure whether this was a misprint or not.

Question 8 asked us to provide URM codes for two functions Think I got this out although for more complicated codes one has to make sure all the inputs are covered especially if one or more of the inputs are zero.
Question 9 Involved generating a primitive recursive function from two others. The definition of primitive recursion is a bit of a mouthful to say the least. Still after a few examples it begins to make sense. In general if a function is defined by recursion it means that a sequence can be generated such that the next term in the sequence can be generated from the others. That is quite straightforward but the definition appears like gobbldeygook and bears at first sight little relation to our intuitive ideas of recursion. However once one realises that the definition of primitive recursion as given in the text is a recipe for generating a primitively recursive function h from two other functions f and g then it makes a lot more sense.

Finally Question 10 was a question asking us to generate the URM code for a function h defined by primitive recursion from two other codes for f and g. There is a somewhat complicated recipe for doing this however if one follows the steps then one eventually gets there. The final part asked us to work out what the function h was Fingers crossed I think I got there.

Overall then should get a grade two, but having left out question 5, unlikely to get distinction.

So first impressions on the whole quite interesting, the number theory part (so far) seems simpler than the computablilty part. But I do wonder whether number theory really counts as a theory, rather than it being a set of miscellenous facts about numbers. It’s not like group theory or analysis, or even quantum mechanics, where given a few axioms, everything follows from them.

As for computability, so far have just scratched the surface, the meat will come in the next two parts. Fortunately I have the Christmas holiday to get to grips with it. I suspect it will be the hardest part conceptually of this course. But it’s good to be challenged.

Bye for now Chris