Hacker News new | past | comments | ask | show | jobs | submit login

> poster clearly doesn’t understand if they are saying

I have a Ph.D. in CS, so you might want to consider the possibility that you are the one who is misunderstanding.

> Touring machines are just one class of computers

So first of all, it's Turing machines, not Touring machines. Named after Alan Turing. And yes, it's true that they are just one class of computer, but the reason Turing machines are a thing is that they are universal. A TM can compute any computable function, where "computable" means computable by any physically realizable model of computation that any human has been able to come up with, including quantum computers. (Quantum computers are just faster for certain problems.) So the details of the TM don't actually matter. There are lots of different computational models that are equivalent to TMs. It's just that the TM model was the first to be proven universal, so that's what everyone talks about. But all physically realizable models of computation that humans have been able to come up with to date are either equivalent to TMs, or strictly less powerful.

So: TMs can't solve the halting problem, and so no other physically realizable model of computation can solve the halting problem either because all known physically realizable models of computation are equivalent to TMs and therefore subject to the same fundamental limitations as TMs. If you knew BB(n) you could solve the halting problem. Therefore you cannot know BB(n). (It's a little but more complicated than that because we can't rule out the possibility that a more powerful model of computation exists and is physically realizable. But that would be the greatest revolution in the history of human intellectual endeavor, so the odds of discovering such a model are pretty low.)




I don’t disagree with what you just said however odds of discovering such a model are pretty low is irrelevant when dealing with abstract computers. Further, suggesting real world physics is unlikely to work isn’t a proof even if I happen to agree.

In the end even if we had a physical machine to produce BB(n) that would not mean it was computable using a Touring machine. Their unrelated concepts.

PS: Looks like auto corrupt strikes again, I really stopped caring at this point.




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: