5 ms·

Turing Uncomputability

45 points by privatdozent 5y ago

throwaway81523 5y ago
This blog used to be called Cantor's Paradise or something like that. Article is an ok popular-level description of uncomputability, focusing mostly on biographical details of early researchers in the field (Turing, Church, etc). As with other articles from the same blog, it mostly rehashes info well known from other sources. There's nothing exactly wrong with it, but I don't really see what is gained. I'm nowhere near a real expert in this topic but almost everything I've seen in the blog so far, I've already seen elsewhere, quite a lot of it in Wikipedia. Nothing is copied or anything like that, but there are only so many ways to tell the same stories.
- stared 5y ago
  Why so much negativity? Especially as it is discouraged here (https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html): > Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something. I know these topics, yet find the presentation nice (structure, style, images). Nothing new? Well, good popular-level articles are often in the "nothing new" category.
  - throwaway81523 5y ago
    I got annoyed that this blog appeared here repeatedly under another name and after a while I stopped clicking on it, but then it showed up again under a new name and I clicked. The author has since explained that the blog is published under the two names on separate hosting sites (medium and substack), which I guess makes sense. That's much better than changing names to slip past people's filters, which we've all seen from time to time. Since you're quoting HN rules I would point to the one saying not to use HN for promotion. These posts do come across to me as promotional, once there have been more than one or two of them. That all said, it is an ok article. I'll leave the other issues up to others going forward.
- privatdozent 5y ago
  Indeed! I’m not claiming to change the world or anything, I just like writing about this stuff
  - throwaway81523 5y ago
    Can I ask why you changed the name of the blog?
    - privatdozent 5y ago
      I didn’t change it, I moved my content to Substack (under the name Privatdozent). Cantor’s Paradise is still on Medium
      - throwaway81523 5y ago
        Fair enough, thanks.
  - ProfHewitt 5y ago
    Dear Jørgen Veisdal: Fair enough. But it would be helpful if the article could be updated to get some information corrected as pointed out in other posts on this page.
- strulovich 5y ago
  I know plenty about computability, and found this to be a fun read. Especially since when being taught it my teachers didn’t spend the time going over the biographies of the people involved.
  - ProfHewitt 5y ago
    History of the people involved is indeed very interesting. Particularly recommend the BBC2 film "Dangerous Knowledge". BTW: The article "Turing Uncomputability" got some of the history wrong about the 1930 interaction between von Neumann and Gödel. See the following: Jan von Plato. "In search of the sources of incompleteness" Proceedings of the International Congress of Mathematicians. 2018.
- dempedempe 5y ago
  Sure you can learn all of this stuff on Wikipedia, but the difference here is that the author has turned it into a narrative, given it character, and a stylish presentation. Like many people today, I have an attention problem. But my eyes were glued to the screen for this whole article.
  - ProfHewitt 5y ago
    Unfortunately, Wikipedia is often not a reliable source of information because its articles are posted and maintained by largely unaccountable anonymous parties.
    - dempedempe 5y ago
      I'd say it's pretty reliable overall.
      - ProfHewitt 5y ago
        It's useful enough to have gained an effective monopoly. However, it cannot be relied upon in specific instances.
galaxyLogic 5y ago
Are quantum computers equivalent to Turing Machines?
- drdeca 5y ago
  In terms of what they can compute, yes, but the time complexity of computing things with a quantum computer can be smaller.
mikewarot 5y ago
I believe that Chaitin’s constant Ω could be approximated, possibly to the point where it could be "computed". It's impossible to emulate a Turing machine, but you can emulate a Turing machine limited to N states. Make A runs of B random bits in said pseudo-Turing(N) machine, observe distribution of programs that halt, or exceed N. Increase A, B or N, and see if some obvious asymptotes arise as you chart the results.
- lisper 5y ago
  Yes, you can do this, but it isn't very interesting because the number you get depends on the details of the computational model that you use to specify the computation (because that's how you define the probability distribution). But people have gone through the exercise, e.g.: https://www.researchgate.net/publication/267327970_Empirical_Estimation_of_the_Halting_Probabilities https://www.researchgate.net/publication/267327970_Empirical...
- drdeca 5y ago
  It is [not computable] in the sense that [there is no program which, given an input n, outputs the first n digits, and then halts]. However, the set of rational numbers less than it, is computationally enumerable, in the sense that there is a program which produces an endless non decreasing sequence of rational numbers which will eventually exceed any rational number less than it. You say “using N states”. This could work, but I think the standard approach is to instead just say to run all programs in a dovetail fashion, and repeatedly count, say, which of the first n programs have halted within n timesteps (and compute the lower bound that that implies on the constant)
ProfHewitt 5y ago
The [Church 1935] proof of the computational undecidability of the halting problem is essentially the same as the [Turing 1936] proof. Consequently, the article under discussion would be better titled "Church/Turing Uncomputability".
ProfHewitt 5y ago
The Church/Turing Hypothesis is false because there are digital computations that cannot be performed by a Nondeterministic Turing Machine. For example, see the following: https://papers.ssrn.com/abstract=3603021 https://papers.ssrn.com/abstract=3603021 https://www.youtube.com/watch?v=AJP1VL7shiI https://www.youtube.com/watch?v=AJP1VL7shiI
ProfHewitt 5y ago
Unfortunately, the article "Turing Uncomputability" is incorrect that [Gödel, 1931] was first to prove inferential undecidablity of mathematical foundations. The [Gödel, 1931] proof using the proposition I'mUnprovable is incorrect for foundations because the proposition does not exist. See the following for correct proofs of inferential undecidablity in foundations: https://papers.ssrn.com/abstract=3603021 https://papers.ssrn.com/abstract=3603021

45 points by privatdozent 5y ago

This blog used to be called Cantor's Paradise or something like that. Article is an ok popular-level description of uncomputability, focusing mostly on biographical details of early researchers in the field (Turing, Church, etc). As with other articles from the same blog, it mostly rehashes info well known from other sources. There's nothing exactly wrong with it, but I don't really see what is gained. I'm nowhere near a real expert in this topic but almost everything I've seen in the blog so far, I've already seen elsewhere, quite a lot of it in Wikipedia. Nothing is copied or anything like that, but there are only so many ways to tell the same stories.

stared 5y ago
Why so much negativity? Especially as it is discouraged here (https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html): > Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something. I know these topics, yet find the presentation nice (structure, style, images). Nothing new? Well, good popular-level articles are often in the "nothing new" category.
- throwaway81523 5y ago
  I got annoyed that this blog appeared here repeatedly under another name and after a while I stopped clicking on it, but then it showed up again under a new name and I clicked. The author has since explained that the blog is published under the two names on separate hosting sites (medium and substack), which I guess makes sense. That's much better than changing names to slip past people's filters, which we've all seen from time to time. Since you're quoting HN rules I would point to the one saying not to use HN for promotion. These posts do come across to me as promotional, once there have been more than one or two of them. That all said, it is an ok article. I'll leave the other issues up to others going forward.
privatdozent 5y ago
Indeed! I’m not claiming to change the world or anything, I just like writing about this stuff
- throwaway81523 5y ago
  Can I ask why you changed the name of the blog?
  - privatdozent 5y ago
    I didn’t change it, I moved my content to Substack (under the name Privatdozent). Cantor’s Paradise is still on Medium
    - throwaway81523 5y ago
      Fair enough, thanks.
- ProfHewitt 5y ago
  Dear Jørgen Veisdal: Fair enough. But it would be helpful if the article could be updated to get some information corrected as pointed out in other posts on this page.
strulovich 5y ago
I know plenty about computability, and found this to be a fun read. Especially since when being taught it my teachers didn’t spend the time going over the biographies of the people involved.
- ProfHewitt 5y ago
  History of the people involved is indeed very interesting. Particularly recommend the BBC2 film "Dangerous Knowledge". BTW: The article "Turing Uncomputability" got some of the history wrong about the 1930 interaction between von Neumann and Gödel. See the following: Jan von Plato. "In search of the sources of incompleteness" Proceedings of the International Congress of Mathematicians. 2018.
dempedempe 5y ago
Sure you can learn all of this stuff on Wikipedia, but the difference here is that the author has turned it into a narrative, given it character, and a stylish presentation. Like many people today, I have an attention problem. But my eyes were glued to the screen for this whole article.
- ProfHewitt 5y ago
  Unfortunately, Wikipedia is often not a reliable source of information because its articles are posted and maintained by largely unaccountable anonymous parties.
  - dempedempe 5y ago
    I'd say it's pretty reliable overall.
    - ProfHewitt 5y ago
      It's useful enough to have gained an effective monopoly. However, it cannot be relied upon in specific instances.

galaxyLogic 5y ago

Are quantum computers equivalent to Turing Machines?

drdeca 5y ago
In terms of what they can compute, yes, but the time complexity of computing things with a quantum computer can be smaller.

mikewarot 5y ago

I believe that Chaitin’s constant Ω could be approximated, possibly to the point where it could be "computed". It's impossible to emulate a Turing machine, but you can emulate a Turing machine limited to N states. Make A runs of B random bits in said pseudo-Turing(N) machine, observe distribution of programs that halt, or exceed N. Increase A, B or N, and see if some obvious asymptotes arise as you chart the results.

lisper 5y ago
Yes, you can do this, but it isn't very interesting because the number you get depends on the details of the computational model that you use to specify the computation (because that's how you define the probability distribution). But people have gone through the exercise, e.g.: https://www.researchgate.net/publication/267327970_Empirical_Estimation_of_the_Halting_Probabilities https://www.researchgate.net/publication/267327970_Empirical...
drdeca 5y ago
It is [not computable] in the sense that [there is no program which, given an input n, outputs the first n digits, and then halts]. However, the set of rational numbers less than it, is computationally enumerable, in the sense that there is a program which produces an endless non decreasing sequence of rational numbers which will eventually exceed any rational number less than it. You say “using N states”. This could work, but I think the standard approach is to instead just say to run all programs in a dovetail fashion, and repeatedly count, say, which of the first n programs have halted within n timesteps (and compute the lower bound that that implies on the constant)

ProfHewitt 5y ago

The [Church 1935] proof of the computational undecidability of the halting problem is essentially the same as the [Turing 1936] proof. Consequently, the article under discussion would be better titled "Church/Turing Uncomputability".

ProfHewitt 5y ago

The Church/Turing Hypothesis is false because there are digital computations that cannot be performed by a Nondeterministic Turing Machine. For example, see the following: https://papers.ssrn.com/abstract=3603021 https://papers.ssrn.com/abstract=3603021 https://www.youtube.com/watch?v=AJP1VL7shiI https://www.youtube.com/watch?v=AJP1VL7shiI

ProfHewitt 5y ago

Unfortunately, the article "Turing Uncomputability" is incorrect that [Gödel, 1931] was first to prove inferential undecidablity of mathematical foundations. The [Gödel, 1931] proof using the proposition I'mUnprovable is incorrect for foundations because the proposition does not exist. See the following for correct proofs of inferential undecidablity in foundations: https://papers.ssrn.com/abstract=3603021 https://papers.ssrn.com/abstract=3603021