3 ms·
Isn't it just possessing both conditionals and loops?
by sgt101 10y ago
Isn't it just possessing both conditionals and loops?
- omegaham 10y agoOne more thing - memory. A Turing Machine is literally just a tape, a movable reader/writer, and a bunch of states that dictate what the reader/writer does. As long as you have memory, the ability to write to memory, conditionals, and some form of looping, whether it's a `while` loop, a `for` loop, or a `jmp` or `GOTO` instruction, it's Turing complete. Note that a conditional jump (`jne`, for example) satisfies both of the latter.
- sgt101 10y agoyup memory. yup. I forgot...
- sova 10y ago"Conditionals, loops, and memory" is an interesting list of requirements, because "memory" can be abstracted into anything. Functional Languages rely on the fact that the same code shall always produce the same outcome, and thus the "tape" has been changed into a series of concrete blocks. That said, I don't think anyone would argue that functional languages are not TC, but it is interesting to consider that the Tape becomes code in Lisp...
- kazinator 10y ago"Turing Complete" refers to a system which can be configured to be come any Turing Machine. When we write a particular program in some language and run it on some input, we have a Turing Machine. If the language lets us create any Turing Machine (i.e. do any Turing computation), then it is a Universal Turing Machine, and Turing Complete. Turing's Tape Machine is a UTM because the tape can be initialized with contents to turn it into any TM. Any calculation for which there is a TM can be done by the UTM (if someone can figure out what to put on the tape).
- jcoffland 10y agoNot necessarily. Purely functional languages, like Lisp, do not have loops. Instead they have recursion. Any iterative algorithm (I.e. one with loops) can provably be converted to a recursive algorithm with out iteration.
- kazinator 10y agoLisp has loops: For instance, the do operator: (do ((i 0 (+ i 1))) ((> i 10)) (print i)) Or the loop macro: (loop for x below 5 and y in '(a b c d e) collecting (list x y)) The 1965 manual for Lisp 1.5 describes the prog construct, which persists into ANSI CL. Inside prog we can have labeled statements to which we can branch unconditionally with go in any direction. Lisp also has mutable variables. The following example from the Lisp 1.5 Programmer's Manual is still valid code today: (LAMBDA (A) (PROG (B) S (SETQ B A) (COND ((NULL B) (RETURN C))) (SETQ C (CONS (CAR A) C)) (GO S)))
- smrq 10y agoWhile another commenter has mentioned that this is technically not correct with Lisp, it holds for the lambda calculus. You don't need loops to be TC if you have recursion. And for that you don't even need named functions-- note the URL of this site!
- kazinator 10y agoHowever, lambda calculus doesn't have code made of data, QUOTE or any of that. Lambda calculus isn't Lisp; it captures the gist of some of the evaluation semantics of Lisp only.
- Shorel 10y agoLisp is more multi-paradigm than pure functional. And we like it that way. It can be functional, object oriented, aspect oriented, etc.