Tagged Questions
6
votes
1answer
90 views
Primitive recursive function which isn't $\Delta_0$
What is the simplest/cutest example (and/or example with the most student-friendly proof that it is an example) of a primitive recursive function which isn't representable by a $\Delta_0$ wff?
0
votes
1answer
113 views
completeness and creative
I'm trying to show that any complete $\Sigma_1^0$ set is creative.
The definition of creative I understand is: if there is a total recurvise function f s.t. f(e) is an element of A iff f(e) is an ...
2
votes
1answer
54 views
Are the brackets in formal box notation of recursive functions omittable?
So we know all recursive functions can be expressed as a finite sequence of symbols for the basic functions and processes composition, primitive recursion, and minimization. What I'm wondering is if ...
1
vote
2answers
78 views
Recursive relation using successor function
What is the recursive relation for $$H(m)=2^{(m^2)}$$ using successor function recursive relation for multiplication: $$mult(x,0)=0; mult(x,S(y))=add(x,mult(x,y))$$ recursive relation for addition: ...
1
vote
1answer
102 views
Representing Recursion and Primitive Recursion diagrammatically
I'm interested in how Recursion, and Primitive Recursion, could be represented diagrammatically. It occurred to me that this would be a good way of seeing the difference. Also, I'm interested in how ...
