[maemre]

I am nerd-sniped with the computability claims here. The last paragraph sums up what I think about what you wrote more broadly.

That description of a "hyper Turing machine" is pretty boring and ridiculous, such a machine trivially solves any computational problem we have because you can embed the problem into the transition function. Here is a sketch of how to do it: Let's call the heads on each tape 0, 1, ...; and let the input be on tape 0. Then the following is a machine that _decides_ a given language:

1. read the input and place the first symbol to tape 1, the second table to tape 2, ... . This takes a single step!

2. Read the whole input by reading a single symbol from each tape, and accept it if it is in the language. This can be done because the transition function can map each string to accept or reject state directly now.

Now, here is the kicker: there are uncountably many "hyper" Turing machines but only countably many strings, so almost all of these machines cannot be described, and there cannot be a universal "hyper" Turing machine. So, I don't think they are that interesting.

Note that the alphabet here is still finite, the infinity is handled by having infinitely many tapes (this is equivalent to going through the trouble of building up something like Goedel encoding). Moreover, I didn't specify the number of tapes here, but countably infinitely many tapes are enough, so you don't need to build an "uncountably-wide" tape. The point I'm trying to make is that if you let a Turing machine-like thing to have countably infinite descriptions, then the description may as well be "look up the solution" so it gets boring from that point on. We need only countably infinite descriptions because a language is countably infinite (because it is a subset of the set of all strings). If one tries to do some shenanigans like making the languages also have higher cardinalities, well just pump up the cardinality of the "hyper" Turing machine to match and you'd end up with the same proofs with slight changes.

> The alphabet our math uses is pretty much all finite. What percent of the axioms and theorems that you know are infinitely long? Shouldn't the overwhelming majority of axioms and theorems be infinitely long (and in particular map onto an uncountable set? (e.g. transcendental numbers).

As for this, we _want_ all of that (and proofs) to be finite. That gives a lot of nice structure we can work with when dealing with first-order logic and proving stuff like compactness and (in)completeness. All of our axioms and theorems are finite (assuming using FOL), we just have countably infinitely many of them (building countably infinitely many theorems is trivial, as for axioms: axiom schemas are just a countably infinite collection of axioms).

This was all to set the record straight when it comes to computability theory. If you want tamer examples of hypercomputation, there is a lot of work on oracle machines and Turing machines that can take infinitely many steps. I think those would be better examples for the "we can reason about 'supra-mathematical' entities using plain old math." claim you are making. Although, I am not buying into this because these are all mathematical entities. We do mathematics because it is an interesting endeavor, and computability is important only in that it helps us understand the math we are doing (can we prove all "true" statements? can we devise an algorithm to solve X?), anything beyond that is still math, and a lot of the notions here (Turing machine as a proxy for algorithm, using first order logic, picking a particular set of axioms) are arbitrary choices that work well so that we can do math with a foundation that won't make us lose much sleep.

[_qfi9]

thanks for the reply,

let me try and rephrase some of what you are saying to check my understanding

set of strings is countably infinite

so my "supra mathematical entity" is boring because for any given problem we could pose it can just function as a lookup table

even if you made an alphabet (strings whose characters had decimal places or something) that was bigger, then it would still be kinda boring cuz the hyper hyper turing machine would still be a lookup table (though maybe even the machine in my example could still just be a lookup table for an uncountably large language on account of having uncountably many tapes/heads).

i'm not sure if it was intended by you but my (somewhat crackpot) takeaway from your response is,

at the limit, computation and memory become the same thing (i was physics undergrad so this still feels profound to me lol (no postgrad yet maybe one day when i am richer) (and maybe also timely w/ gpt3 XD))

also i think i am still digesting notion that there is no general version of hyper turing machine

[maemre]

> even if you made an alphabet (strings whose characters had decimal places or something) that was bigger, then it would still be kinda boring cuz the hyper hyper turing machine would still be a lookup table (though maybe even the machine in my example could still just be a lookup table for an uncountably large language on account of having uncountably many tapes/heads).

That's pretty much what I wanted to mean. Although I called it "boring", it was not to take a jab but more so because there is not much effort to spend to understand the limitations of such a machine once you can encode the whole language into the machine's look-up table. Also, such an extension makes us lose the ability to simulate other extended machines in general. Extensions to Turing machines are interesting because of how they may alter the limits of computability (in a completely hypothetical setup) and complexity, and I had some fun when writing the response although I called that specific machine model boring because it ended up being too powerful to be interesting (from a computability theory perspective).

[zzzzzzzza]

i had some more crackpot thoughts if you don't mind hearing them lol

the set of all strings is countably infinite like the natural numbers

however human language when actually spoken can contain recursive implicit meanings and subtext, so maybe even though it's just strings, if you made the implicit context explicit it would be uncountably infinite, much like the real numbers, even though in practice the meaning a human can grok from any given sentence is bounded like a ieee floating point number.

but i find it somewhat interesting that whereas all ieee floats have a certain amount of meaning they can carry around/a set amount of decimal places, the way we encode implicit meanings and tones into language is uneven, it's not character by character (but it can be if you add an accent or tone to a character even in non tonal languages),

like, what if you could design a number system more like human language where the decimal places somehow only showed up under certain conditions (maybe you could argue complex numbers are kinda like that, since the imaginary or real parts will appear and re apper under certain operations)

could you design a number system or an algebra in such a way that it was up for interpretation lol (or if not why not)

one thing is that you can interpret numbers in terms of geometry, but the interpretation is one to one, and thus boring compared to the interpretability of strings.

also maybe lambda calculus is somewhat interpretable in this way, and it can encode numbers and algebraic rules

maybe logical conclusion of this train of thought is the IO monad XD