Let's just summarise here. We know that primitive recursive functions are URM-computable in which case the set of primitive recursive functions is countably infinite. Previously we saw that the set of all functions is not countably infinite and so not all functions are primitive recursive. In the opening to unit ML3 of the mathematical logic course it is shown, using the diagonal argument again, that not all URM-computable functions are primitive recursive.
The key to progress in understanding the relationship between recursive functions and URM programs is to realise that not all programs halt for a given input (that is reach the stage where there are no more instructions to process and an output is obtained). Some can loop round indefinitely and never reach an instruction that points outside of the program. To incorporate this into our idea of recursive functions, partial functions are introduced. A URM program computes a partial function f if for a given input, the program either halts and produces the output of f or it does not halt and f is undefined.
This either finding an output or not is equivalent to unbounded searches and the new process that is introduced is called minimisation (previously we had bounded minimisation). A new definition of recursive function is introduced (as opposed to primitive recursive) which says that a function is recursive if it can be obtained from basic primitive recursive functions using the operations of substitution, primitive recursion and minimisation on a function a finite number of times.
This allows us to finally answer the question that we originally asked. Are all URM-computable functions recursive? The answer is yes! This is part of the course that I think I really understood. The reason is relatively simple (although the proof was quite long and only sketched out); if you are at a particular stage of processing a URM program you can always determine what instruction you should process next based on the current values in the registers and what the current instruction says you should do. Unless you are at a jump instruction the next instruction to process is the one following the one you are at. Jump instructions depend on the contents of the registers. The key is that you can again provide a code number for all these situations of the program (imagine the trace table and a code that went with each entry in the table). This is clearly a recursive process except that, as we have said, an output may or may not be defined.
The chapter goes on to discuss Kleene's Normal Form Theorem, a consequence of which is that each recursive function can be obtained from the basic primitive recursive functions using the operations of substitution, primitive recursion and at most one minimisation on a function. The discussion was then broadened to Church's Thesis which says that the notion of an algorithmically computable function coincides with that of a recursive function. This is not a mathematical theorem but a statement that is believed to be true. Finally, algorithmically undecidable problems were looked at and this is where I came close to chucking the book out of the window. I struggled with some of these proofs.
Wednesday 30 October 2013
Good progess but it is hard going
I thought I would give a quick update on where I am at now with the courses. I finished unit 3 of Mathematical Logic but it was a huge struggle. The last parts had me ready to chuck the book out of the window in frustration. I don't think I really got all of it and at times some of the proofs seemed like pulling rabbits out of hats - you had no idea where they came from and they were as impenetrable as magic.
So I soldiered on to unit GR2 of the groups course, thinking it might be a relief but some of the proofs we are asked to come up with for ourselves are impossible at times and there is only a limited number of hours in the day I can struggle over them, so it isn't very satisfying. GR2 was about Abelian and cyclic groups and their classification. I have now moved on to book 4 of the logic course on formal systems and this has been relatively light relief.
On the other hand the TMA's are going well. I have completed both of the first TMAs for the two courses and done over half the second TMA for the groups course. The groups TMAs are, by far, much easier than the number theory and logic ones. I enjoyed the flag colouring exercise but how we are to count distinguishable flags without using any of the results from the unit and awarding only 4 marks for it beggars belief. Perhaps I missed something.
So I soldiered on to unit GR2 of the groups course, thinking it might be a relief but some of the proofs we are asked to come up with for ourselves are impossible at times and there is only a limited number of hours in the day I can struggle over them, so it isn't very satisfying. GR2 was about Abelian and cyclic groups and their classification. I have now moved on to book 4 of the logic course on formal systems and this has been relatively light relief.
On the other hand the TMA's are going well. I have completed both of the first TMAs for the two courses and done over half the second TMA for the groups course. The groups TMAs are, by far, much easier than the number theory and logic ones. I enjoyed the flag colouring exercise but how we are to count distinguishable flags without using any of the results from the unit and awarding only 4 marks for it beggars belief. Perhaps I missed something.
Saturday 19 October 2013
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.
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.
Tuesday 15 October 2013
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.
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.
Tuesday 8 October 2013
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.
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.
Subscribe to:
Posts (Atom)