On Fri, Jan 14, 2011 at 1:13 AM, Robert McIntyre <r...@mit.edu> wrote: > As HTML-y as it it is, PHP is Turing complete and thus a "real" > programming language.
So are LaTeX, Javascript, and a few others, but from what I've seen they're all meant for specific purposes rather than general-purpose software engineering. > It's got foreach loops, mutable arrays, and boolean logic, and that's > one particular set of operations to simulate a Turing machine. I read somewhere that it suffices to have a program counter, a register, four stacks, jump-back-or-forth-N-steps with a small bounded N, if register zero then next instruction otherwise skip one instruction, increment register (which wraps at some value), and peek or pop for each of the four stacks (to the register). Alternatively, a program counter, a stack, a cursor into an infinite deque, and these eight instructions: increment at cursor, decrement at cursor, jump amount at cursor, if zero at cursor next instruction else skip, cursor left one, cursor right one, push program counter, pop program counter. The universal Turing machine concept suggests that there's an instruction set for which only the infinite deque is needed, with cursor-left, cursor-right, and some additional instructions, but no long range jumps within the deque, and instructions also fetched from the deque with no separate program counter. It would be a real bitch to program, though. The general rule seems to be that a) there has to be at least one if-something condition that alters flow, say by optionally skipping one instruction that can be a longer-range jump and may be followed by another such; b) there has to be a backward jump possibility; and c) there has to be some kind of memory -- either bidirectionally infinite and cursor-navigable like a giant ArrayList, or at least four stacks that can be separately peeked and popped. With just one stack you can apparently get a big subset of fully general computation but not the whole deal. There also has to be d) arithmetic of some kind, on the memory content and interacting in some way with the if condition. > http://en.wikipedia.org/wiki/Turing_machine > http://aturingmachine.com/ I see your Turing machine and raise you this: http://www.rezmason.net/wireworld/ -- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
