Turing Uncomputability | Hacker News Reader

Turing Uncomputability

privatdozent.co

45 pointsprivatdozent22 comments

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.

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...

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)

Are quantum computers equivalent to Turing Machines?

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

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

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://www.youtube.com/watch?v=AJP1VL7shiI

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".

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.

Indeed! I’m not claiming to change the world or anything, I just like writing about this stuff

Can I ask why you changed the name of the blog?

I didn’t change it, I moved my content to Substack (under the name Privatdozent). Cantor’s Paradise is still on Medium

Fair enough, thanks.

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.

Why so much negativity? Especially as it is discouraged here (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.

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.

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.

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.

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.

Unfortunately, Wikipedia is often not a reliable source of

information because its articles are posted and maintained by

largely unaccountable anonymous parties.

I'd say it's pretty reliable overall.

It's useful enough to have gained an effective monopoly.

However, it cannot be relied upon in specific instances.

Reply on news.ycombinator.com