5 ms·

Your critique of hypercomputation applies all the same to Turing complete machines. A Turing machine can never be implemented and is a totally theoretical model

by setra 9y ago

Your critique of hypercomputation applies all the same to Turing complete machines. A Turing machine can never be implemented and is a totally theoretical model. At best we can implement a class of machine below called a "Linear bounded Turing machine". For these machines the halting problem is solvable (it can just take a while). You could even implement a linear bounded Turing machine as an FSM it would just take an ungodly number of states.

eximius 9y ago
This is unintuitive to me. Source? (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?)
- monochromatic 9y ago
  There are only finitely many states. Detect loops.
  - eximius 9y ago
    Okay. "Loop detected. It terminates conditionally on the value of `a`". 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.
    - anewhnaccount2 9y ago
      I think the answer is you can solve the halting problem if you have finite memory. You just need to consider every possible memory value. Eventually no new memory values can be introduced, so the next state must be one of the already inspected memory values. Of course all this takes at least exponential time and so is outside our normal computability assumptions.
      - gizmo686 9y ago
        Wouldn't the halting problem take at most exponential time? 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).
        Dylan16807 9y ago
        That's the point, yes. A real machine has finite memory, while a proper Turing machine can always advance the tape to get more memory. You can solve the former in ridiculous but non-infinite time, but not the latter.
        pas 9y ago
        The general halting problem takes a potentially unbounded input. 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.)
    - dllthomas 9y ago
      By "detect loops" the parent meant "detect repetition of exact state". We have a fixed state machine. If we find ourselves in the same state, at the same location in the same tape, we must not halt because we will proceed in a loop indefinitely. If we have a finite tape, there are only finitely many states the entire system can occupy, so we must be able to exhaust them (or halt first, or loop first) in finite time.
Boxxed 9y ago
"It can just take a while" is a pretty egregious understatement. As the busy beaver question shows, even an extremely simple turing machine with just a handful of states can execute for a completely unfathomable number of steps. https://en.wikipedia.org/wiki/Busy_beaver https://en.wikipedia.org/wiki/Busy_beaver
- setra 9y ago
  That is gaming the definitions of "states" a bit. Your example has a official finite number of "states" combined with an unbounded tape of extra states while only counting the FSM controlling it. That tape is part of the state, the machine can edit / read the tape in its decision procedure. 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.
  - Boxxed 9y ago
    I think you're confusing "states" with cells on the tape. They are completely independent. All turing machines have an unbounded tape, but a well-defined number of states that act as an automaton controlling the head on the tape.
deleted 9y ago
[deleted]
frankmcsherry 9y ago
> You could even implement a linear bounded Turing machine as an FSM it would just take an ungodly number of states. 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 https://en.wikipedia.org/wiki/Linear_bounded_automaton [1]: https://en.wikipedia.org/wiki/Finite-state_machine https://en.wikipedia.org/wiki/Finite-state_machine [2]: https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_lang...
- setra 9y ago
  This is correct from the unbound theoretical tape perspective. I should have expanded my point you are very correct. If you look in the context of physical realization (finite) a tape that can be written is some form of RAM. Beyond O(1) complexity all of these machines can express each other with different amounts of RAM. Even in the theoretical model an FSM can accept balanced parentheses of finite depth. My FSM point is basically wrong though.
  - deleted 9y ago
    [deleted]
chriswarbo 9y ago
Turing machines are a useful simplification: they eliminate the (literal) edge-case that we hit the end of the tape. We can either think of this as having "infinite tape", or we can imagine a "tape factory" on either end which extend the tape faster than the TM can read it. 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.

by setra 9y ago

eximius 9y ago

This is unintuitive to me. Source? (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?)

monochromatic 9y ago
There are only finitely many states. Detect loops.
- eximius 9y ago
  Okay. "Loop detected. It terminates conditionally on the value of `a`". 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.
  - anewhnaccount2 9y ago
    I think the answer is you can solve the halting problem if you have finite memory. You just need to consider every possible memory value. Eventually no new memory values can be introduced, so the next state must be one of the already inspected memory values. Of course all this takes at least exponential time and so is outside our normal computability assumptions.
    - gizmo686 9y ago
      Wouldn't the halting problem take at most exponential time? 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).
      - Dylan16807 9y ago
        That's the point, yes. A real machine has finite memory, while a proper Turing machine can always advance the tape to get more memory. You can solve the former in ridiculous but non-infinite time, but not the latter.
      - pas 9y ago
        The general halting problem takes a potentially unbounded input. 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.)
  - dllthomas 9y ago
    By "detect loops" the parent meant "detect repetition of exact state". We have a fixed state machine. If we find ourselves in the same state, at the same location in the same tape, we must not halt because we will proceed in a loop indefinitely. If we have a finite tape, there are only finitely many states the entire system can occupy, so we must be able to exhaust them (or halt first, or loop first) in finite time.

Boxxed 9y ago

"It can just take a while" is a pretty egregious understatement. As the busy beaver question shows, even an extremely simple turing machine with just a handful of states can execute for a completely unfathomable number of steps. https://en.wikipedia.org/wiki/Busy_beaver https://en.wikipedia.org/wiki/Busy_beaver

setra 9y ago
That is gaming the definitions of "states" a bit. Your example has a official finite number of "states" combined with an unbounded tape of extra states while only counting the FSM controlling it. That tape is part of the state, the machine can edit / read the tape in its decision procedure. 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.
- Boxxed 9y ago
  I think you're confusing "states" with cells on the tape. They are completely independent. All turing machines have an unbounded tape, but a well-defined number of states that act as an automaton controlling the head on the tape.

deleted 9y ago

[deleted]

frankmcsherry 9y ago

> You could even implement a linear bounded Turing machine as an FSM it would just take an ungodly number of states. 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 https://en.wikipedia.org/wiki/Linear_bounded_automaton [1]: https://en.wikipedia.org/wiki/Finite-state_machine https://en.wikipedia.org/wiki/Finite-state_machine [2]: https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_lang...

setra 9y ago
This is correct from the unbound theoretical tape perspective. I should have expanded my point you are very correct. If you look in the context of physical realization (finite) a tape that can be written is some form of RAM. Beyond O(1) complexity all of these machines can express each other with different amounts of RAM. Even in the theoretical model an FSM can accept balanced parentheses of finite depth. My FSM point is basically wrong though.
- deleted 9y ago
  [deleted]

chriswarbo 9y ago

Turing machines are a useful simplification: they eliminate the (literal) edge-case that we hit the end of the tape. We can either think of this as having "infinite tape", or we can imagine a "tape factory" on either end which extend the tape faster than the TM can read it. 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.