To be clear, these things have formal definitions, and this statement is not correct.
1. A linear bounded automaton[0] is a Turing machine that can only overwrite symbols presented on its input tape as input. However, the definition of the automaton is still required to be finite, but it is required to operate on unboundedly large input tapes.
2. A finite state machine[1] is a model of computation where the sequence of input symbols are observed once and the machine is at all times in one of a finite number of states. It is equivalent to a TM that can only move right (and consequently cannot read anything it writes to the tape).
They are different, formally[2]. There are languages that a LBA can accept that a FSM cannot accept (famously, the strings of balanced parentheses cannot be recognized by a FSM).
[0]: https://en.wikipedia.org/wiki/Linear_bounded_automaton
[1]: https://en.wikipedia.org/wiki/Finite-state_machine
[2]: https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_lang...
Mathematically, this sort of simplification is used a lot: when our model requires some sort of bound, we can work under the assumption of it being 'sufficiently large' that we can ignore edge-cases. Another example is the set of "real" numbers, which we can represent as decimals and assume a sufficiently large number of decimal places to avoid rounding. In fact, similar to the "tape factories" of a TM, we can think of each real number as having a "decimal-place factory" which produces new digits more quickly than we can read them (for example, during Cantor diagonalisation).
The infinities in hypercomputation don't seem to be providing such a simplification. Their 'sufficiently large' assumption seems to be the number of steps which can be executed in a unit of time, which avoids the edge-case of non-halting programs. I'm not sure that's a useful simplification.
Noting this a few more states than a handful are possible. For example my laptop with bitpacking could track the visited or not visited flag for 64000000000 states without even using disk. Tracking a 33 bit FSM.
I agree though that linear bounded Turing machines having a solution for the halting problem is not actually that useful for real computers considering by the time a few registers had been iterated over the sun would have exploded.
(I can understand why we might not be able to build a Turing machine because we don't have infinite tape, etc, but if a program never halts but merely needs finite space, how do you prove that, in general?)
I would think that deciding if a loop halts is equivalent to the halting problem (just wrap your program in a loop). Merely detecting loops seems insufficient.
Of course all this takes at least exponential time and so is outside our normal computability assumptions.
We know that a program with n bits of memory has at most 2^n states, so we can maintain an n bit counter that is incremented once on each program iteration. If this counter reaches (2^n)-1, then the program does not terminate. (Depending on how you define things, there is an off-by-one error here; just run the program a few times before you start counting).
That's why it's impossible to solve.
If it were finite (bounded), then you could do an enumeration of the possible programs of that bounded size, and you could make a program that simply looks up that list. (Sure, maybe the making of the list would be a bit problematic, because it'd take ... multiple eons, lesser gods would die, rise and die again during that time, but it's still finite.)
Plenty of mathematics does not "model anything real", but you may still want to understand it. The paper starts with an analogy to non-Euclidean geometry, which once "had no physical basis", until we learned more about the universe and found that it did.
Mathematics isn't a pitch deck.
The author repeatedly makes the point that we don't know, for sure, that this is the case. And that "we haven't built it yet", sans additional explanation, is pretty shoddy evidence for the non-existence of something.
And that, if such a thing did exist, its existence may well be "very fundamental to the structure of the universe and should not be ignored".
I agree with both you and the author.
I don't think we'll ever build device capable of general-purpose "harnessable" hypercomputation. And I don't think any of the ideas described in this paper are in any meaningful sense physically realizable.
But I also allow the possibility that I am wrong, especially on the first count. And if I am wrong, even just on the first count, then some of the theory surveyed in this paper might turn out to be useful.
The Bekenstein bound (https://en.wikipedia.org/wiki/Bekenstein_bound) and the Holographic Principle (albeit the latter not being a concrete part of physics yet) provide strong reasons as to why analog computing is not a viable path to the realization of "hypercomputation". Besides, a few loopholes nonwithstanding (https://pdfs.semanticscholar.org/a4b2/4409635c442b45f6fa4271...), the physical existence of legitimate hypercomputation stands in almost direct opposition to the Church-Turing thesis.
It's not claimed sans explanation. Hypercomputation would break a lot of physics. Others have mentioned the Bekenstein Bound, but just consider just basic concepts like signal to noise ratios. You'd need infinitely precise detectors for hypercomputation, detectors capable of distinguishing literally any signal, not matter how small, among any amount of noise, no matter how overwhelming.
These properties simply stretch credulity, to say the least.
[1] https://plato.stanford.edu/entries/computation-physicalsyste...
If you can't measure anything with arbitrary accuracy then that seems more than enough reason to assume you can't go beyond finite (digital) accuracy.
For example, classical field equations apparently can behave in non-computable ways, so long as their initial conditions are sufficiently wierd. I'm not sure if QM as we undestand it can handle such fields: but then "as we understand it" is a bit too limiting.
So why haven't we observed these wierd non-computable fields? My guess is that it's because they don't exist. But it might be that we just haven't recognized them, perhaps some of those puzzling things in physics -- like QM perhaps itself is caused by naughty non-computable stuff going on where we haven't yet recognized it.
Is it sort of like the n-body problem of classic chaotic behavior?
Regarding the first question, I am only repeating pop-science here.
I've read (In something by Roger Penrose, presumably The Emperors New Mind, but maybe in The Road to Reality) that the Maxwell Equations are uncomputable only if the initial conditions are functions that don't have Fourier transforms.
So really it is the field dynamics that are non-computable. I might have been talking nonsense when I the fields themselves were non-computable. But then again, the kinds of functions that don't have a Fourier transforms are also very rough, jaggedy things that probably can't be approximated by any algorithm.
And speaking of rough jaggedy functions, that's what you get if you evolve a chatoic system to infinity. So maybe there is some connection after all, but it is well beyond my understanding.
So that kind of computability might be the mathematical algebraic computability (as in does this monstrosity have a closed form?), which can always be approximated (of course with fast accumulating errors).
If anything is a problem it is the attractive name, that pushes non-technical journalists into paying attention to it.
> Under the banner of "hypercomputation" various claims are being made for the feasibility of modes of computation that go beyond what is permitted by Turing computability. In this article it will be show n that such claims fly in the face of the inability of all currently accepted physical theories to deal with infinite precision real numbers. When the claims are viewed critically, it is seen that they amount to little more than the obvious comment that if non-computable inputs are permitted, then non-computable outputs are attainable.
The original idea in Turing's thesis was that the Turning Machine was something that could actually be implemented, and indeed you can find many examples of people's side projects where such machines can be made and can actually compute things.
On the other hand, hypercomputation has no physical basis. So what's the point of using it to model anything real? It's next to useless.
[1]: http://www1.maths.leeds.ac.uk/~pmt6sbc/docs/davis.myth.pdf