-horses t1_iycz7ys wrote on November 30, 2022 at 2:11 PM

Reply to comment by sdmat in [r] The Singular Value Decompositions of Transformer Weight Matrices are Highly Interpretable - LessWrong by visarga

Hypercomputation is an extremely extraordinary and extremely specific claim.

>But if we verify the operation of a plausible embodiment of hypercomputation on a set of inputs that we happen to know the answer for, that does tell us something. If the specific calculation we can validate is the same in kind as the calculations we can't validate, a mere difference in input values to which the same mechanism of calculation applies, then it is a form of proof.

Here's a machine that produces the number of steps for each of the known 2-symbol Busy Beaver machines, and then keeps giving answers using the same mechanism.

On input n:
    answers = [1, 6, 14, 107]
    return answers[n % 4]

Hypercomputation confirmed? (Note: we could easily change the last line so further outputs were monotonically increasing and larger than the step number for the current candidate for BB_2(5), while keeping correctness on the first four. Imagine an infinite series such machines, each more cleverly obfuscatory than the last; they exist.)

>The first computer was verified without computer assistance.

The first computer was verified by human computers with greater computational power than it had.

edit: And rewinding a bit, the original claim was that there's an effectively realizable device, that is, one which can be implemented, and whose implementation can be accurately described with finite time, space, and description length, ie by a TM, the usual sense of 'effective'. If this were the case, the TM could just simulate it, proving it was not a hypercomputer. This is the sense in which the claim is flat-out wrong, aside from the difficulty of trying to evaluate it with 'evidence'.

sdmat t1_iyf7dck wrote on November 30, 2022 at 11:05 PM

> Hypercomputation confirmed? (Note: we could easily change the last line so further outputs were monotonically increasing and larger than the step number for the current candidate for BB_2(5), while keeping correctness on the first four. Imagine an infinite series such machines, each more cleverly obfuscatory than the last; they exist.)

No, because there is no plausible computational principle giving the answer to the general Busy Beaver problem embodied in that system. Notably, it's a turing machine.

An inductive proof needs to establish that the inductive step is valid - that there is a path from the base case to the result, even if we can't enumerate the discrete steps we would take to get there.

By analogy proof of hypercomputation would need to establish that the mechanism of hypercomputation works for verifiable examples and that this same mechanism extends to examples we can't directly verify.

Of course this makes unicorn taxonomy look down to earth and likely.

> edit: And rewinding a bit, the original claim was that there's an effectively realizable device, that is, one which can be implemented, and whose implementation can be accurately described with finite time, space, and description length, ie by a TM, the usual sense of 'effective'. If this were the case, the TM could just simulate it, proving it was not a hypercomputer. This is the sense in which the claim is flat-out wrong, aside from the difficulty of trying to evaluate it with 'evidence'.

That's a great argument if the universe is Turing-equivalent. That may be the case, but how to prove it?

If the universe isn't Turing-equivalent then it's conceivable that we might be able to set up a hypercalculation supported by some currently unknown physical quirk. Doing so would not necessarily involve infinite dimensions - you are deriving those from the behavior of Turing machines.

An example non-Turing universe is one where Real numbers are physical, I.e. it is fundamentally non-discretizable. I have no idea if that would be sufficient to allow hypercomputation, but it breaks the TM isomorphism.

-horses t1_iyf9a66 wrote on November 30, 2022 at 11:19 PM

>No, because there is no plausible computational principle giving the answer to the Busy Beaver problem embodied in that system. Notably, it's a turing machine.

Yes, there is no plausible computational principle giving the answer to the Busy Beaver problem in any system, because it is not computable. The point was that you can't trust a machine simply because it produces the known answers correctly and keeps going the same way.

>Doing so would not necessarily involve infinite dimensions - you are deriving those from the behavior of Turing machines.

You need an infinite resource available to get anywhere past finite automata, you just don't have to actually use infinite resources until you get past TMs. Non-automatic models of computation aren't relevant to measurable behavior of dynamical systems in the real world.

>That's a great argument if the universe is Turing-equivalent. That may be the case, but how to prove it?

No, it isn't. It's an observation that 'effective' has a standard definition which precludes hypercomputation. Any effective computation is simulable by a Turing machine; that's not the physical Church-Turing thesis, it's the vanilla version. (edit: and the reason I put the word in there originally is that any AGI implemented with computers would be in that boat, while many models AGI theorists prefer would not be, but are intended to represent real-world systems that would. Thus, they are often claiming to have effective means to non-effective ends.)

>An example non-Turing universe is one where Real numbers are physical, I.e. it is fundamentally non-discretizable. I have no idea if that would be sufficient to allow hypercomputation, but it breaks the TM isomorphism.

This is an example of falling back on infinite information in finite space. If space is continuous, it contains all the uncomputable reals. If you doubt this requires infinite information, consider that these include the incompressible strings of infinite length. A system moving through such a space would adopt states that require infinite information to describe infinitely often. It still wouldn't allow us to show any hypercomputation, though; our ability to observe and communicate remains finite, and all finite observations are explicable by finite machines, well within computability.