1

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.

Jacob
  • 11
  • 1
  • 5
    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. – Neil Hoffman Apr 09 '15 at 03:18
  • 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! – Jacob Apr 14 '15 at 00:57

0 Answers0