[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
update
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.pgp>
- References:
- update
- From: kmedcalf at dessus.com (Keith Medcalf)
- update
- From: Valdis.Kletnieks at vt.edu (Valdis.Kletnieks at vt.edu)
- update
- From: pete at altadena.net (Pete Carah)