# All Questions

35 questions
Filter by
Sorted by
Tagged with
47 views

### How to show that a partial function is recursive?

I try to prove that this function is recursive: $$f(x_1,x_2)= \begin{cases} 2x_1-x_2 & \text{if x_1 \geqslant \sqrt{x_2}} \newline \bot & \text{otherwise} \end{cases}$$ I think that I need ...
20 views

### Converting a function with single parameter to a function with multiple parameters

I have been solving some algorithm questions recently and a pattern I have observed in some problems is as follows: Given a string or a list, do an aggregation operation on each of its elements. Here ...
72 views

460 views

### Side effect and recursion

My algorithm professor said a recursive function should not have side-effects since it's a methodological error because recursion is "pure". Anyway I don't understand why, even because I find side-...
225 views

### Problems understanding proof of smn theorem using Church-Turing thesis

I am reading Barry Cooper's Computability Theory and he states the following as the s-m-n theorem: Let $f:\mathbb{N}^2\mapsto\mathbb{N}$ be a (partial) recursive function. Then there exists a ...
215 views

### How can the class of tail recursive functions be compared to the classes of PR and R?

How can the class of tail recursive functions (TR) be compared to the classes of primitive recursive functions (PR) and recursive functions (R)? The computation of a PR function always halts. This ...
102 views

### Algorithm to compute a recursive function on a given set [closed]

I am working on a property of a given set of natural numbers and it seems difficult to compute. There is a function 'fun' which takes two inputs, one is the cardinal value and another is the set. If ...
I am working on a recursive formula associated with discrete mathematics which seems very difficult to compute. The formula is as follows $F_{i,j}(m)=\sum_{t=j}^{m}\left [ x_{ij}.\sum_{k=1}^{m}\sum_{... 2answers 709 views ### The minimization operator is an effective operator Assume$\{f_i^{(n)}\}_{i=0}^\infty$is a Gödel enumeration of the$\mu$-recursive functions of$n$arguments, such that the$S^m_n$theorem and the universal function theorem hold. Denote the set of (... 1answer 293 views ### Prove$\varphi(x)$to be primitive recursive Let$\varphi(x)=2x$if$x$is a perfect square,$\varphi(x) = 2x+1$otherwise. Show$\varphi$is primitive recursive. In proving$\varphi$to be a p.r. function I think it could come in handy the ... 2answers 2k views ### Show$x^y$is a primitive recursive function As this thread title gives away I need to prove$x^y$to be a primitive recursive function. So mathematically speaking, I think the following are the recursion equations, well aware that I am ... 1answer 196 views ### Clarifications on primitive recursive function definition I am studying primitive recursive functions and there's something that I don't quite understand: let's take the function that computes$x+y$, then, in order to show that$f(x,y)=x+y\$ is primitive ...
Let $$f(x)=\begin{cases} x \quad \text{if Goldbach's conjecture is true }\\ 0 \quad \text{otherwise}\end{cases}$$ Show that f(x) is primitive recursive. I know a primitive recursive ...