1
$\begingroup$

In this presentation by Vladimir Voevodsky [1], he mentions a result that there is a formula over the natural numbers with a single free variable such that one can prove that there is no algorithmic method of determining set membership for any natural number.

Can anyone know of a reference to this result?

[1] https://www.youtube.com/watch?v=O45LaFsaqMA @ about 2/3 through the lecture... lost the exact location in the video.

Improve this question
$\endgroup$
2
  • 5
    $\begingroup$ Hi Jacob, Welcome to MO. As Bjørn Kjos-Hanssen points out this question is appears to be a duplicate. In order to keep the site tidy, we try to avoid that. Hopefully, Bjørn's link answers your question. However, if you do really need a reference in the literature, then you could consider editing the question acknowledging Bjørn's answer to the linked question. $\endgroup$
    – Neil Hoffman
    Commented Apr 9, 2015 at 3:18
  • $\begingroup$ Thanks! I didn't try searching for it first here; frankly, I'm surprised something that specific had been asked before... but then again, Voevodsky is a popular guy! $\endgroup$
    – Jacob
    Commented Apr 14, 2015 at 0:57

0

Reset to default

Browse other questions tagged .