Computability - Primitive recursive functions, need help :)

MumboJumbo · 8 Oct 2011 at 22:40

Hey, well I do a maths degree and I've just changed one of my modules to a module called "Computability and Unsolvability" and quite frankly I'm completely lost on the lingo because I missed the first week of lectures due to just having changed module. Unfortunately, despite it actually being advertised as a maths module it appears the lecturer presumes you know logic and I haven't done any modules on it, nor have my friends.

So I was hoping some of you might be able to explain some things to me so I'll just list them:

1) What does sg and sg bar (bar over the sg) mean?

I need to show that sg(bar)(n) = { 1 if n=0 , 0 otherwise} is primitive recursive and quite frankly I'm lost as to where to start on account of the fact i have no idea what sg(bar) means.

2) I have to also show that n! = factorial of n is primitive recursive and this is my idea, correct me if I'm wrong:

Using the "inital function" the "succesor function" which states that n' = n+1 for all n in the natural numbers is primitive recursive I can break down n! into successor functions:

0! = 1
1! = 1
2! = 2
.
.
.
(n+1)! = n! x (n+1)

I'm unsure however as to how to really tie that off and state that it is primitive recursive.

I'll leave it at that for now. I have 9 questions to answer, each written in language I don't particularly understand but I'm hoping that if I work out how to do these two I can work out the rest.

Thanks.

D.P. · 8 Oct 2011 at 22:58

I am trying to remember my undergrad days were I had courses n this.

For the 1st one I am not sure if you are missing sme information?

For the 2nd you are on the right track, you need to do a proof by induction method. Show the base cases hold and the recursive case hold true. n+1 is the standard successor function and you have show how (n+1) can be calculated from the succesor and recursive function. Not to sure there is so much more to it.

ViZioN8 · 8 Oct 2011 at 23:10

sg(bar) simply means the inverse of SG. If SG is 1, SG bar is 0 and vice-versa.

When I did it at Uni it was logic in terms of electrical circuits so you either had high (1) or low (0).

There's some more info here: http://en.wikipedia.org/wiki/Logic_level

MumboJumbo · 8 Oct 2011 at 23:37

I've given you all the info I have been given for the first question. It is very vague. So my answer to the second question is just about then once I put some wording around it?

Humm so how do I know if SG is 1 or not in this case :/. Oh so hopeless! haha.

I've got 6 of these little proofs of primitive recursiveness just for the first question, then 8 others ontop of that like proving the fibonacci sequence is primitive recursive.

I think I best go sleep on this and do it tomorrow. I just checked out my quantum mechanics work and it made me want to die, nearly 3 pages of questions. The worst part is that that one isn't actually coursework but I know if I don't do it I simply won't learn it.

MumboJumbo · 9 Oct 2011 at 19:20

Sigh, still horribly lost

. All my lecturer tells me to do is to buy his book. Pretty sure he's meant to be teaching instead of selling his book.

:EDIT:

Ok, I think I've worked out the first one. It's primative recursive because the function is either equal to a constant or the zero function.