1
$\begingroup$

Suppose I have a (recursive) function $f:\Bbb N\rightarrow\Bbb N$ whose range is infinite, and I want to list all the function values without repeating.

That is, if $f(0)=1,f(1)=1,f(2)=5,f(3)=6,f(4)=6,f(5)=2$, I need a program with outputs $1,5,6,2$ I need it to firstly list $1$, then $5$, then $6$ and then $2$.

My idea is: Start from $0$, firstly output $f(0)$, and then increase $0$ by $1$ to get $1$, look at what is $f(1)$, if it is equal to $f(0)$, then we do not output it, otherwise we output $f(1)$. And then look at $f(2)$, if it is equal to at least one of $f(0),f(1)$, then we do not write it out, otherwise we output $f(2)$. But so far I found my knowledge too poor to write a program in psudocode...

My attempt:

x := 0; 

while (n < x) 

{ if (f(n)=f(x)); 

 n := n+1; 

else

return f(x)}

I think maybe this code is problematic. Could someone please tell me some way to write it? This is such a minor part of my math course that we are not taught how to write psudocodes and now I feel a bit frustrated...

Other simple ways to do it would also be appreciate. Thanks in advance to you all who may help!

To sum up, I wish to see a psudocode to out put all the values of the function:

$f':\text{n↦the nth value in the enumeration that isn't a repeat of a previous value}$ where $f$ is a recursive function. Apologize for my poor knowlege of computing. I have no backgroud of computing and even not know what is "memory", only psudocode is readable for me... And actually I just need the psudocode program to prove that this function is recursive.

Thank a lot to you all who leave answers and comments!

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ Keep in mind that, if the image of $f$ contains only finitely many values, after you have listed them all, the listing program has to diverge -- there's no way to check that we have listed them all, so the listing program has to query $f$ forever just in case some new value appears. This argument is not a proof, but at least can provide some intuition. $\endgroup$
    – chi
    Jul 17, 2017 at 15:09
  • $\begingroup$ What is your question? Do you want a code in a certain programming language? Do you want just an algorithm and you want to code it yourself? As far as I understand you want to display the range of the function, so what if the range is infinite? $\endgroup$
    – fade2black
    Jul 17, 2017 at 15:40
  • $\begingroup$ Seems like a programming question to me? $\endgroup$
    – Raphael ♦
    Jul 17, 2017 at 20:16
  • $\begingroup$ Hint: use memory. $\endgroup$
    – Raphael ♦
    Jul 17, 2017 at 20:17
  • 1
    $\begingroup$ @Raphael Yes, that's what I meant. My point is that, if the "index of the function value we want" is larger than the number of distinct elements that $f$ produces, then the enumeration has to diverge. (This is not as issue per se, but something to keep in mind anyway) $\endgroup$
    – chi
    Jul 17, 2017 at 20:22

1 Answer 1

Reset to default
1
$\begingroup$

You can implement your task by keeping track of the values that have appeared so far. You maintain an array $S$ that starts empty. You compute the values $f(0),f(1),f(2),\ldots$, and for each value, you check whether it is already in $S$; if so, you don't do anything; otherwise, you print it, and add it to $S$.

Improve this answer
$\endgroup$
8
  • $\begingroup$ What if the range is infinite? $\endgroup$
    – fade2black
    Jul 17, 2017 at 15:41
  • 2
    $\begingroup$ This isn't a problem, since the set of values that have appeared so far is always finite. $\endgroup$
    – Yuval Filmus
    Jul 17, 2017 at 15:42
  • $\begingroup$ That is only an assumption, but the OP should stipulate that the range of the function is finite. For example, the range $f(0) = 0, f(n) = n + f(n-1)$ is infinite. Or I am missing something. $\endgroup$
    – fade2black
    Jul 17, 2017 at 15:51
  • 2
    $\begingroup$ No, I disagree. The set $\{f(0),\ldots,f(n)\}$ is finite for every $n$. $\endgroup$
    – Yuval Filmus
    Jul 17, 2017 at 15:51
  • 1
    $\begingroup$ I think that "list" here means "enumerate", like in recursive enumerability. Listing all the values, even with a finite range, is uncomputable. $\endgroup$
    – Yuval Filmus
    Jul 17, 2017 at 15:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.