News for hackers. Stuff that matters.
Re:Hypercomputation: Computing more than the Turing machine ... by setra on Sunday September 10, 2017 @08:56PM (#15215122)
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.
Re:Hypercomputation: Computing more than the Turing machine ... by frankmcsherry on Monday September 11, 2017 @01:27AM (#15216157)
> 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

[1]: https://en.wikipedia.org/wiki/Finite-state_machine

[2]: https://en.wikipedia.org/wiki/Pumping_lemma_for_regular_lang...

Re:Hypercomputation: Computing more than the Turing machine ... by setra on Monday September 11, 2017 @01:49AM (#15216250)
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.
Re:Hypercomputation: Computing more than the Turing machine ... by chriswarbo on Monday September 11, 2017 @03:03AM (#15216583)
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.

Re:Hypercomputation: Computing more than the Turing machine ... by Boxxed on Sunday September 10, 2017 @11:04PM (#15215597)
"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

Re:Hypercomputation: Computing more than the Turing machine ... by setra on Sunday September 10, 2017 @11:53PM (#15215774)
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.

Re:Hypercomputation: Computing more than the Turing machine ... by Boxxed on Tuesday September 12, 2017 @02:48PM (#15230344)
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.
Re:Hypercomputation: Computing more than the Turing machine ... by eximius on Sunday September 10, 2017 @10:56PM (#15215563)
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?)

Re:Hypercomputation: Computing more than the Turing machine ... by monochromatic on Sunday September 10, 2017 @11:01PM (#15215585)
There are only finitely many states. Detect loops.
Re:Hypercomputation: Computing more than the Turing machine ... by eximius on Monday September 11, 2017 @01:55AM (#15216279)
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.

Re:Hypercomputation: Computing more than the Turing machine ... by anewhnaccount2 on Monday September 11, 2017 @02:02AM (#15216317)
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.

Re:Hypercomputation: Computing more than the Turing machine ... by gizmo686 on Monday September 11, 2017 @04:20AM (#15216895)
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).

Re:Hypercomputation: Computing more than the Turing machine ... by pas on Monday September 11, 2017 @05:55AM (#15217288)
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.)

Re:Hypercomputation: Computing more than the Turing machine ... by Dylan16807 on Monday September 11, 2017 @05:54AM (#15217285)
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.
Re:Hypercomputation: Computing more than the Turing machine ... by dllthomas on Thursday September 14, 2017 @12:01AM (#15244913)
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.