Are all URM computable functions recursive? (Part 2)

This is where ML2 becomes more interesting. So far it had been shown that all primitive recursive functions are URM-computable. But are all URM-computable functions primitive recursive? Are there any functions of any sort that are not primitive recursive?

To answer this question required a diversion into infinite sets and Cantor's theory of countably infinite sets. This is the rather neat idea that a set is countably infinite if you can find a one-to-one correspondence between it and the set of natural numbers {0, 1, 2, 3, ...}. So, rather bizarrely, the set of even numbers {0, 2, 4, ...} is countably infinite since there is a one-one function f(n)=n/2 that maps the even numbers to the natural numbers. In fact, any infinite subset of the natural numbers is countably infinite.

Now the text goes on to show how we can assign each URM program a unique code number using the properties of prime numbers. Recall that the fundamental theorem of arithmetic means that a given natural number can only be written as positive powers of primes in one way. So, by assigning each instruction in a program a unique positive number (also referred to as a code number) and then creating a new number which is a product of primes raised to the power of these instruction numbers, then each program can be assigned a unique code number drawn from the set of natural numbers. So, of course, this subset is countably infinite. The advantage is that given a code number, we can recover the program uniquely.

So we come to the question as to whether there are any functions of any sort which are not primitive recursive. Here we use a diagonal argument of Cantor's (the same one he used to show that the set of real numbers is not countably infinite) to show that there are, i.e. that the set of functions is not countably infinite (as the set of primitive recursive functions is).

The rest of unit ML2 works towards proving that the set Prog of code numbers of URM programs is primitive recursive. This involves showing that the characteristic function of the set of prime numbers, the function p which enumerates the prime numbers and the set Instr of code numbers of URM instructions are all primitive recursive. The function p that enumerates the primes is simply the one that says, for example, that the 4th prime number is 7, i.e. that P(4)=7. The important concepts of bounded minimisation on a function or a relation are introduced. This is the the process of looking for a minimal solution of a function within a bounded (i.e. known) range.

So what does it mean to say that the set Prog of code numbers of URM programs is primitive recursive? I think it means that there is a primitive recursive function that can determine what these code numbers are and that in turn means that such a function is URM-computable, i.e. that there is a URM program that can compute them.

Are all URM-computable functions recursive? (Part 1)

I have just got to that point in ML3 of M381 where this question has been answered affirmatively and it has been an interesting read getting there. I can't help feeling that this is really important but as yet I haven't understood all the implications of the theory. Before I forget I will try and outline how we arrived at that point by way of a summary, so I don't forget the basic ideas.

What is a URM-computable function? A URM is an unlimited register machine and a URM-computable function is a function that can be computed by such a machine (in other words the machine and the function produce the same output for the same given input). So what is it? Well, its a theoretical computer that can process a program with a very limited set of instructions (4 in fact) but has an unlimited (but finite) set of registers in which to store numbers (the integers 0, 1, 2, ...). The four instructions are Z(n) (Zero n; replace the number in register n by 0), S(n) (Successor n; add 1 to the number in register n), C(m,n) (Copy m to n; copy the number in register m to register n) and J(m,n,q) (Jump m, n, q; jump to instruction q if the numbers in register m and n are equal, otherwise go to the next instruction).

ML1 deals with some simple functions of two variables that can be computed by such machines; add, multiply, max, min etc. by showing how they can be programmed directly. However, the focus of the investigations is to find new ways of creating URM-computable functions by building them up from more basic functions. Firstly it is shown how programs can be concatenated by placing one program after another, so that the output of one becomes the input for another. Then, using this technique, two important theorems are proved - that new URM-computable functions can be obtained from existing ones by substitution and primitive recursion. For substitution, the new URM-computable function is obtained from existing ones by substituting URM-computable functions for the inputs of another. For primitive recursion, a sequence of new URM-computable functions are obtained by basing each new function on the previous one, which is again a form of substitution and requires two URM-computable functions 'to start the process off'.

The more interesting and, at times, difficult material appears in unit ML2. As said before, instead of programming functions directly, new URM-computable functions are obtained from existing ones by substitution and primitive recursion. The basic URM-computable functions considered were the zero, successor and projection functions which are the one-line programs containing the instructions Z(1), S(1) and C(m,1), respectively. Confusingly, perhaps, these are called the basic primitive recursive functions. Another function is said to be primitive recursive if it can be obtained from these basic ones by substitution and primitive recursion a finite number of times. ML2 goes on to show how more and more complicated primitive recursive functions can be obtained from these basic ones.

An important idea was introduced as to how to define such functions by cases. This is of the form 'if such and such is true then the function has this form, but if this is true then it has this form'. This required a detour into characteristic functions of sets and relations and determining if such functions are primitive recursive. This culminated in a proof that a function defined by cases is primitive recursive if the functions and relations that defined it (i.e. the cases) were primitive recursive.

Crisis, what crisis?

How can I be having a crisis at this stage, I hear you say? Well it's perfectly possible. I pretty much know how much work I have left to do over the 8 months of these two courses. I reckon that to cram 32 books into 8 months I need to be reading roughly 6 pages a day (3 from each course) and as I have already done a third of the books, that leaves 4 pages a day. So, since my last post I have been trying to do just that but I am struggling! What with trying to answer the exercises, read the proofs and then start to think about the coursework, it ain't easy.

So lo and behold I have reasoned that I am going to have to adopt a new strategy which I don't like very much. It comes in three parts 1) don't try to answer all the exercises 2) when answering an exercise just sketch out the answer and don't try to answer it as you would properly 3) skip the proofs where possible. Yuk! I don't like this prescription very much but I would rather not be sitting for hours on end each day getting back ache. And surprise, surprise, I have found that by doing this I can get 4 pages done a day - welcome to the real world!!

Progress. Ok, NT4 is done and I have nearly worked through GE1 (counting theorem again, but in a slightly more advanced and detailed way). I have been away for a weeks holiday in Norfolk and so I decided, in my non-holiday moments, to see I could finish TMA01 of M336 and amazingly I have! I have also done all the number theory questions of TMA01 of M381. I think M381 is harder! So now I feel a bit more relaxed and I can crack on with what I think will be increasingly more difficult material.

Eyes down

My course materials have now arrived for M381 and M336 and the course websites opened today and so off we go again. It is good to be in touch with people once more. It is hard doing all this preparation in advance without contact with anyone and but now that I have the actual books in front of me and the forums are open, it is much more motivating.

So how well did I do in my 6 months or so of preparation. Well, I got through NT1, 2, 3 and ML1 and 2 of M381 and IB1, 2, 3, 4 and GR1 of M336, so 10 books in all, just under a third of each course. So this will give me a head start and make the progress smoother, I hope! But I do realise that even with this advantage, I am going to have to speed up from the way I have been working so far, which has been at my usual leisurely pace.

What I have found surprising in what I have seen so far is how much more difficult the set problems are. It has been a bit of a shock to the system that there are problems that I just can't do without having a peek at the solutions. I could devote more hours to trying to solve the problems without help but I don't think this is good use of my time. So I have had a reality check about what I can and can't do and I think this is a good thing.

So now its back to the books. I am reading NT4 on Fermat's and Wilson's theorems. Strangely enough the last book I read of M336, GR1 was all about the theory of integers again, a repeat really of NT1 and 2, but actually, the way it was dealt with in GR1 was more difficult! The problems were a pain and, not like me, I couldn't be bothered to attempt the last four in the book - I felt too drained!

Another thing about these two courses is that it is all about proofs (both in the text and the set problems). So if you don't like proofs you are in for a hard time!

At some point I would like to write a summary of ML1 and 2. There was a lot of interesting stuff and writing a summary would help me to recall it all.

Good luck to you all and I look forward to meeting up with Chris and Dan again.

More on Generating Subgroups

I seem to be blogging more about the groups course M336 rather than the number theory and mathematical logic course M381, but I get the feeling this will all change at some point as I get further into mathematical logic.

Ok, time for an update. I finished the first mathematical logic unit of M381 without too much difficulty. I think the hardest part is dealing with a whole load of new concepts. Once you get the hang of these then it seems to be alright. I then moved onto unit 4 of groups and geometry and this was quite a time consuming book both from the length of it and the considerable number proofs that you have to wade through and also come up with yourself. A lot of the material was revision going over topics such as cosets, normal subgroups, quotient groups, isomorphisms and homomorphisms. However, there was quite a lot of new material and perhaps the most important was proving that you can generate a subgroup of a group using elements of that group (see my previous post).

The approach to this theory was different from what I expected and quite subtle. Firstly, the subgroup of a group G generated by an underlying set of elements S is defined to be the 'smallest' subgroup of G containing the set S. This is denoted <S>. The first step is to prove that there is a unique smallest subgroup of G that contains S. The trick is to consider all the subgroups of G that contain S. This collection is certainly not empty since it contains G (as G is a subgroup of itself). Now consider the intersection H of all these subgroups that contain S. The intersection of a set of subgroups is itself a subgroup (and this was proved in the unit). So H is a subgroup of G. It also contains S because our collection of subgroups each contained S. Further, H must be the 'smallest' subgroup of G containing S because H is the intersection of our set of subgroups and so is contained by those subgroups. Hence <S>=H.

Although this tells us that <S> exists it does not tell us what <S> looks like! The subgroup axioms come in handy here. <S> must contain the identity of G, e say, and the inverse of the elements of S in G. This means that <S> must also be generated by these elements (namely e, the elements of S and the inverse of the elements of S). We can call this set S'. The text then goes on to show that <S> is generated by the set of words in S', W(S'). As words in English are created by taking any finite arrangement of letters (in principle) drawn from our 26 letter alphabet, so the words in W(S') are formed by taking any finite arrangement of elements from S' (but in English we might suspect that eeeeeaaaaeeeooooaeaor isn't a word as it is in group theory!). It turns out that <S>=W(S').

Having been writing this blog over the last few days I have got further into unit 2 of mathematical logic and, surprise, surprise, I have found some of it increasingly difficult (if not impossible)! However, having said that I can't help thinking it is blooming neat and I am glad I am doing it as I think it has resonances in some of the things I have thought about number theory.

T minus 86 days and counting

I received confirmation the day before yesterday that the SAAS are paying my course fees for M381 and M336 this October and so I am all set for my next year's work. I am very grateful to the Scottish system of support for the likes of me.

I am progressing ok. I finished unit 3 of the number theory half of M381 on congruence. This was fairly straight forward and didn't offer any particular difficulties. In the mean time I have also finished unit IB3 of M336 on frieze groups and again this wasn't particularly challenging. I can now see where this course is going with its classification of friezes and wallpaper patterns. I did always wonder what Alan, our tutor for M208, was always going on about when he said that there were 17 different types of wallpaper pattern and now I have an inkling of what he may mean. I have also now got through a fair chunk of unit 1 of the mathematical logic half of M381 on computability. This is ok as it is basic linear programming.

Going back to friezes, I thought I would show you an example of a frieze that can be found in our flat.

My Dad (who knows these things because he is an architect) pointed out to me that this type of cornice is called "egg and dart" which I think is an apt description. From a mathematical point of view, if you take the decoration bit in the middle as the frieze (ignoring the fact that it obviously doesn't extend indefinitely to the left and right), then it has a number of different symmetries. For example, if you take a basic element of an egg bounded by half a dart on either side, then you can translate this element horizontally left and right by multiples of the distance between two adjacent darts. This is what defines a frieze. There are also, obviously, reflections in a vertical axis (either through a dart or through the centre of an egg). There are, however, no rotational symmetries or reflections or glide reflections in a horizontal axis.

Each frieze can be analysed according to its group of symmetries and an algorithm is given in the unit for identifying the type of frieze according to its group. This is a type 2 frieze or in international notation a pm11. There are seven types of frieze in all, as defined by their symmetry group.

Generating subgroups

I have just finished going through book 2 of M336 Groups and Geometry and I am making reasonable progress. As usual I seem to be working at roughly half the speed that you are supposed to but I expect I will get through enough material to make life easier when the course actually starts in October. So now I have read four books in total from M336 and M381 and I am alternating between the two courses; i.e. when I finish a book from one course I start on a book from the other course. I will be looking at book 3 from M381 next which is on congruence.

Before I leave book 2 of M336, there are a few things I want to say about it. Firstly, I have noticed that the exercises in these level 3 courses require much more from the student. At level 2 it was pretty much spoon feeding - i.e. the books would give examples of how to do something and then there would be exercises where you repeat what you just learnt. Here at level 3 the questions are more demanding as the way to do an exercise is often left up to the student. I welcome this as I like thinking things through for myself, but at times it can be very time consuming. What has surprised me is that a certain amount of 'hand-waving' has appeared both in the text and in the answers to exercises; i.e. rather than thrashing out an answer exhaustively, a bit of 'well, the answer is like this because of such and such.' It can be a bit frustrating if the details are skipped over and a bit of shock after the intense rigour of M208.

I want to put down here some bits of this book which I thought ventured slightly into the hand-waving arena. This part of the book was the most difficult and the most time consuming and so it is worth going through so that later I have something to look back on for revision.

How can you generate subgroups? In M208 we have already met cyclic subgroups which are generated from integer powers of an element in a group. For example, if we consider the group of symmetries of the regular hexagon and label a rotation about its centre through π/3 as r then we can generate a cyclic subgroup from r as

$$<r>=\left\{r^{0}, r, r^{2}, r^{3}, r^{4}, r^{5}\right\}$$

Now the new idea is to expand this notion of generating subgroups to include two or more distinct elements of a group. In the text it says that "Informally, we define the subgroup generated by x,y,... to be the set obtained by forming all possible combinations of copies of x,y,.. and their inverses." In the margins it does say that a formal definition is given later in unit IB4 but I found it difficult to understand this without some formal definition. Here is my version of a formal definition for two distinct elements of a group x and y:-

$$<x,y>=\left\{uv:u,v \in \left\{ (x)^{i},(y)^{i}:i,j \in Z \right\} \right\}$$

Now it is clear that integer powers of x and integer powers of y are just the cyclic subgroups <x> and <y> and so we can rewrite this as

$$<x,y>=\left\{uv:u,v \in <x>\cup<y> \right\}$$

In other words we are taking combinations of elements taken from a union of the subgroups generated by x and y. This does not mean that the resulting subset is a subgroup. This still has to be verified by seeing if the subset satisfies the subgroup properties. One thing that becomes clear straight away is that <x,y> contains the elements of <x> and the elements of <y>. This is because if u and v are drawn from <x>, say, then because <x> is a cyclic subgroup, then the combinations of uv are also in <x>. What is new are products of elements which are not common to both sets.

Let's take an example. If we consider the regular hexagon again and call the symmetry that is a reflection in the horizontal axis s, then s is self-inverse and

$$<s>=\left\{e,s\right\}$$

If we also consider the half-turn about the centre r³ then this is also self-inverse and

$$<r^{3}>=\left\{e,r^{3}\right\}$$

But what about <r³,s>? We see from the above discussion that this is going to contain e, r³, and s but it also must contain combinations of elements which are not common to both sets, namely sr³ and r³s. These turn out to be the same element since sr³ is a reflection of some sort which is self-inverse so

$$sr^{3}=(sr^{3})^{-1}=r^{-3}s^{-1}=r^{3}s$$

Hence we have the subset

$$<r^{3},s>=\left\{e, r^{3}, s, r^{3}s\right\}$$

which does indeed turn out to be a subgroup of the symmetries of the regular hexagon and is isomorphic to the Klein group.