update

Mon Sep 29 16:09:34 UTC 2014

On Mon, 29 Sep 2014 00:32:49 -0500, Pete Carah said:

> The halting problem comes up in connection with _data_ handling in any
> computer with even a language interpreter (e.g. is browser-based
> javascript complete enough for the halting problem to apply to it?

The halting problem applies to *any* language/system that's Turing-complete.
And the bar is *really* low for that. If you have an increment or decrement
operator, a branch operator, and a test-and-skip-on-zero, you're
Turing-complete.

In fact, you can design a CPU with *one* opcode that's Turing complete. Part
of the fun is that since there's only one opcode, you can omit it, and then
instructions consist only of operand addresses.  Then remember that von Neumann
architectures allow self-modifying code....

http://en.wikipedia.org/wiki/One_instruction_set_computer
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 848 bytes
Desc: not available
URL: <http://mailman.nanog.org/pipermail/nanog/attachments/20140929/391677f6/attachment.sig>