3 ms·

> In the early 70s, computer designers rediscovered that it’s impossible to build an arbiter that is guaranteed to reach a decision in a bounded length of time.

> In the early 70s, computer designers rediscovered that it’s impossible to build an arbiter that is guaranteed to reach a decision in a bounded length of time. (This had been realized in the 50s but had been forgotten.) > a device for making a binary decision based on inputs that may be changing So it's the result of the halting problem, applied to a continuous function in hardware?

jacobparker 7y ago
It's an interesting thought but I'm not aware of any way to plausibly connect the two, mathematically.
- Supermancho 7y ago
  > it’s impossible to build an arbiter that is guaranteed to reach a decision in a bounded length of time. "To build" would be a series of logic gates, in hardware, which is why the halting problem could apply. The fact that the outputs are expected to be considered a continuous function is incidental and (as stated) can only be considered a discontinuous function, despite the target guarantees and specifications might state.
  - jacobparker 7y ago
    Right, but the reasons why are different from the halting problem. As stated in the OP, "the key assumption in this argument is continuity". I'm not sure what you mean by the outputs being "expected to be considered a continuous function". In both the halting problem and this case the outputs are discrete (e.g. binary: halts/does not halt, left/right, etc.) There are other impossibilty results, e.g. the FLP theorem. Despite having computing-based interpretations they're not all related to the halting problem. :) That being said, maybe it's possible to generalize the halting problem to a continuity in some reasonable way and get something like Buridan's principle. It's not obvious to me how that would be done but I'd be interested to see!
    - Supermancho 7y ago
      > this case the outputs are discrete (e.g. binary: halts/does not halt, left/right, etc.) As you vary the inputs, the outputs change. This results in a continuity. There is a question of ranges, but this is handled by a type system (even if that type is a pointer, you run through all memory for your function inputs).
dooglius 7y ago
No, the halting problem says that one cannot determine whether an _arbitrary_ program halts, while this says that one cannot build a _particular_ physical device that is guaranteed to output in bounded time.
- Supermancho 7y ago
  > No, the halting problem says that one cannot determine whether an _arbitrary_ program halts While the specific definition differs, the fundamental assertion is similar. Thanks for the downvotes for what was an earnest question whoever. SMH
- deleted 7y ago
  [deleted]

jacobparker 7y ago

It's an interesting thought but I'm not aware of any way to plausibly connect the two, mathematically.

Supermancho 7y ago
> it’s impossible to build an arbiter that is guaranteed to reach a decision in a bounded length of time. "To build" would be a series of logic gates, in hardware, which is why the halting problem could apply. The fact that the outputs are expected to be considered a continuous function is incidental and (as stated) can only be considered a discontinuous function, despite the target guarantees and specifications might state.
- jacobparker 7y ago
  Right, but the reasons why are different from the halting problem. As stated in the OP, "the key assumption in this argument is continuity". I'm not sure what you mean by the outputs being "expected to be considered a continuous function". In both the halting problem and this case the outputs are discrete (e.g. binary: halts/does not halt, left/right, etc.) There are other impossibilty results, e.g. the FLP theorem. Despite having computing-based interpretations they're not all related to the halting problem. :) That being said, maybe it's possible to generalize the halting problem to a continuity in some reasonable way and get something like Buridan's principle. It's not obvious to me how that would be done but I'd be interested to see!
  - Supermancho 7y ago
    > this case the outputs are discrete (e.g. binary: halts/does not halt, left/right, etc.) As you vary the inputs, the outputs change. This results in a continuity. There is a question of ranges, but this is handled by a type system (even if that type is a pointer, you run through all memory for your function inputs).

dooglius 7y ago

No, the halting problem says that one cannot determine whether an _arbitrary_ program halts, while this says that one cannot build a _particular_ physical device that is guaranteed to output in bounded time.

Supermancho 7y ago
> No, the halting problem says that one cannot determine whether an _arbitrary_ program halts While the specific definition differs, the fundamental assertion is similar. Thanks for the downvotes for what was an earnest question whoever. SMH
deleted 7y ago
[deleted]