# Function is recursive iff its graph is recursively enumerable

So I understand that a function is recursive if there exist a Turing Machine that accepts it and halts on every input, since function is defined everywhere. But how to prove that function is recursive if and only if the language {x#f(x) |x∈(Г -{#})*)} (graph) is recursively enumerable?

In order to prove your claim, you need to prove two things:

1. If a function is recursive then its graph is r.e.

2. If the graph of a function is r.e. then it is recursive.

Let's see what you have to do to prove these two claims.

Claim 1. Suppose that $f$ is recursive, i.e. it is computable by some program. You have to come up with another program that enumerates $x\#f(x)$. For example, assuming the inputs are natural numbers, it could output $1\#f(1),2\#f(2),3\#f(3),\ldots$.

Claim 2. Suppose that $\{x\#f(x)\}$ is r.e., that is, some program enumerates $x\#f(x)$ for all legal inputs $x$, in some order. Given an input $y$, we need to use this enumeration to compute $f(y)$. It is natural to wait for $y\#f(y)$ to be enumerated and extract $f(y)$.
{"ft_lang_label":"__label__en","ft_lang_prob":0.93276083,"math_prob":0.99822557,"size":2082,"snap":"2019-26-2019-30","text_gpt3_token_len":514,"char_repetition_ratio":0.17613089,"word_repetition_ratio":0.01724138,"special_character_ratio":0.24303554,"punctuation_ratio":0.12731482,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.99928683,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-07-22T03:42:41Z\",\"WARC-Record-ID\":\"<urn:uuid:b1e79149-ec53-43dd-ba6d-055758e793bc>\",\"Content-Length\":\"144337\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:16315556-2ab2-49a2-aab8-83109f222aca>\",\"WARC-Concurrent-To\":\"<urn:uuid:f8d68b43-ba50-46e4-b1d6-5db39a41cced>\",\"WARC-IP-Address\":\"151.101.193.69\",\"WARC-Target-URI\":\"https://cs.stackexchange.com/questions/33000/function-is-recursive-iff-its-graph-is-recursively-enumerable\",\"WARC-Payload-Digest\":\"sha1:3ELK3GAFCTKQSGOCCNCMUWXFPANDOEKW\",\"WARC-Block-Digest\":\"sha1:UVPVGTVI4TNI2ER77424S7E5MQNLVOQX\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-30/CC-MAIN-2019-30_segments_1563195527474.85_warc_CC-MAIN-20190722030952-20190722052952-00232.warc.gz\"}"}