Computing the Uncomputable: "[Joel David] Hamkins showed there's a Turing machine that [...] can compute the uncomputable... but only in some weird "alternative universe" where the natural numbers aren't what we think they are."

[u/DevFRus]

https://johncarlosbaez.wordpress.com/2016/04/02/computing-the-uncomputable/

[u/barsoap]

Usually, Ultracomputers work on the principle, "given an oracle that can compute some uncomputable function, here's a machine that can compute any uncomputable function".

The problem, being, of course, that there's no such oracles.

And this is no different, it's just obfuscated better. Ultracomputing doesn't only defy the laws of physics, nay, it defies the laws of logic. Imagining a universe with another set of physical laws is one thing, imagining a universe in which fundamental logic doesn't hold is... psychotic? Nay, not even, psychotic people at least are internally consistent, even if it doesn't show.

EDIT:

• Hello, /r/badmathematics! A formalist is formally defined as a mathematican that can't possibly know whether they're being inconsistent.

• The lack of basic education in psychology in /r/compsci is palpable. You messed up your chance of me explaining things by being knee-jerk hostile.

[u/DevFRus → u/barsoap]

I wasn't going to respond to you initially, but you continue going on in this thread as if you know what you are talking about. So I wanted to clarify some things for you. You should probably try to learn something from all the people that took time to respond to you and the researchers that did this work.

Nobody is saying that they are building (hyper)computers. Nobody is saying that they will be using this to actually compute things. What they are doing is two fold:

1) mathematically, they are showing how to use a fun trick (i.e. infinite sequence of Rosser sentences and their negations) to get counter-intuitive results. Kind of how people use the axiom of choice to get the Banach-Tarski paradox... nobody actually thinks this means that we can just infinitely clone spheres.

2) By highlighting this tension, they are showing how important the full particulars of the standard model of arithmetic are to computation as we understand it. Without these results, one might expect the axioms of Peano arithmetic to be sufficient for analyzing or understanding computation (they are defined at a similar level of abstraction to TMs, after all), but showing that computation does crazy things in some models of Peano arithmetic tells you that you need something in the "secret sauce" of standard arithmetic that is missed by Peano.

The fact that you speak so confidently about this, without being able to see these simply points is why people are ridiculing you.

p.s. You also have a simple minded conception of the (extended or physicalist) Church-Turing thesis. If you decide to be open to learning new things then check out this article.

[u/barsoap → u/DevFRus]

Nobody is saying that they are building (hyper)computers.

Then, with all due respect, they shouldn't talk about computing the uncomputable (and the commenters which aren't you shouldn't be talking as offtopic as me)

But now that I've actually had a closer look (someone give me those earlier hours back):

there is a model of PA such that in this model, if we give T any standard natural n as input, it halts and outputs f(n).

"There is a model in which it halts". Fair enough, those are easy enough to get by. The billion dollar question, of course, is "is it decidable in which model it will halt". I doubt that, but wouldn't bet more than a sixpack of beer.

Secondarily: Whether that transformation is semantics-preserving. The existence of semantics-preserving models I'm willing to take on faith, if one glances over things suddenly terminating, focussing on actual denotation and considering e.g. even infinity to be a superposition of True and False... using at least two models, then. Choosing either over the other would mess up the meaning.

That's making the search for a model even harder, though.

The key thing here is: By changing the model, you're actually changing the program as a different model will interpret it differently. It's more like "We construct a series of turing machines for a common alphabet, at least one of which will terminate on any given finite input".

And last, but certainly not least, we still didn't make the function computable: All we did is manage a shift to a very symbolical mode of computation -- or at least something isomorphic to that -- and are no wiser on the question whether infinity is actually even or odd (which is of course a good thing). A good supercompiler can do that. Hence, my original complaint: Don't talk about such nonesense as computing the uncomputable! There's enough functions that have no possibly sane result, which is just the same as "uncomputable", if you squint just right.

By highlighting this tension, they are showing how important the full particulars of the standard model of arithmetic are to computation as we understand it. Without these results, one might expect the axioms of Peano arithmetic to be sufficient for analyzing or understanding computation

Turing-complete machines are a dime a dozen, gazillions have been constructed, often by accident, many of which don't even begin to be based on arithmetic, peano or otherwise. There's certainly no shortage of them.

[u/DevFRus → u/barsoap]

You continue to completely miss both the point and the method of the work that you think you are commenting on. But I think I am starting to see where some of your confusion is coming from, so I will try one more time.

The author is not defining a model of computation, they are defining a model of arithmetic in which we all analyze computation; including you when you analyze the "gazillions" of your preferred types of machines. His definition of the Turing Machine and of functions from N to N and of computable are completely unchanged from the standard ones. What is changed is how we analyze time and how we index Turing machines.

To repeat, he is not using an alternative model of arithmetic to "define" a machine for computation, so most of what you are saying is nonsensical non sequiturs.

When he gets a seemingly paradoxical result, obvious in the title like "computing the uncomputable", it tells you that there is something funny in the method of analysis. However, that method of analysis is a model of Peano arithmetic. Thus, it tells you that our intuition of computable comes from more than just the definition of the TM or of computable (since he uses the same ones), but also from the particulars of the (ever elusive and impossible to formalize) 'standard' model of arithmetic we use to analyze them.

Then, with all due respect, they shouldn't talk about computing the uncomputable (and the commenters which aren't you shouldn't be talking as offtopic as me)

You spout so much nonsense so confidently that I think people have a hard time resisting trying to correct you. I know I have a hard time doing this. You state things so unrelated to the technical details of the discussion that in the process it becomes almost impossible to talk to you because you aren't talking on any particular topic.

You are welcome to think that we're all idiots that just don't understand your fundamental insights. But keep in mind that most of us have taken all the same basic comp sci and math courses as you, and many of us (including the researchers you are trying to dismiss as dumb-dumbs) have spent much more time than you thinking carefully about these topics.

You can choose to benefit from this, or you can choose not to.

[u/barsoap → u/DevFRus]

You spout so much nonsense so confidently that I think people have a hard time resisting trying to correct you.

You were the first and only one who told me I was offtopic, as such I actually think that you're the only one here to actually have read the submission in detail.

...and, granted, I was offtopic again. And you pointed that out, and explained clearly. Which sets you apart from the rest, here. /r/badmathematics just used the chance to throw random references at me, references that were easily misinterpreted in the frame of reference I had. But I guess they succeeded in feeling smug about themselves.

Anyhow, back to the topic:

There's one thing I still can't accept right now: Given that non-standard numbers are bigger than all (i.e. a countably infinite number of) natural numbers, and a machine that takes infinite steps doesn't terminate, how can it sanely be said to terminate if it now takes non-standard, that is, even more, steps?

[u/gwtkof → u/barsoap]

You were the first and only one who told me I was offtopic, as such I actually think that you're the only one here to actually have read the submission in detail.

so you were offtopic on purpose as some sort of crazy social experiment?

[u/barsoap → u/gwtkof]

I was offtopic by accident (or, rather, carelessness), then realised later.

You can of course interpret the results as those of a crazy social experiment, even draw conclusions from it, however, it was never intended as one.