4 ms·

As a Computer Scientist, I actually find the distinction Turing and non-Turing to be rather obscure. Perhaps I am in the ignorant minority on this.

by sova 10y ago

sgt101 10y ago
Isn't it just possessing both conditionals and loops?
- omegaham 10y ago
  One 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 ago
    yup 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 ago
  Not 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 ago
    Lisp 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 ago
    While 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 ago
      However, 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 ago
    Lisp is more multi-paradigm than pure functional. And we like it that way. It can be functional, object oriented, aspect oriented, etc.
deleted 10y ago
[deleted]
scott_s 10y ago
A Turing-complete programming language just means that you can compute anything that can be computed using that language. In other words, it can be used to write arbitrary computations. You don't need much to achieve this; off the top of my head, I think that being able to read and write to storage, basic addition, conditionals and loops are enough. (Formally, it means that your language can be used to simulate a single-taped Turing machine.) A non-Turing-complete language is any language which does not have one of those capabilities. Because the bar is so low, most languages you have used in your life are Turing-complete. For example, you can imagine a simple calculator-like language for just writing mathematical expressions. It can do all basic math operations, has conditions, but no ability to repeat things (no loops or recursion). That language is not Turing-complete. You can trivially prove that programs from such a language will finish - they can't not! there's no ability to impede progress.
- blackkitty 10y ago
  You can actually have a turing complete instruction set with only one instruction. I am not sure as to the practicality but here is a wikipedia link to read. https://en.wikipedia.org/wiki/One_instruction_set_computer https://en.wikipedia.org/wiki/One_instruction_set_computer

As a Computer Scientist, I actually find the distinction Turing and non-Turing to be rather obscure. Perhaps I am in the ignorant minority on this.

by sova 10y ago

As a Computer Scientist, I actually find the distinction Turing and non-Turing to be rather obscure. Perhaps I am in the ignorant minority on this.

sgt101 10y ago

Isn't it just possessing both conditionals and loops?

omegaham 10y ago
One 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 ago
  yup 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 ago
Not 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 ago
  Lisp 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 ago
  While 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 ago
    However, 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 ago
  Lisp is more multi-paradigm than pure functional. And we like it that way. It can be functional, object oriented, aspect oriented, etc.

deleted 10y ago

[deleted]

scott_s 10y ago

A Turing-complete programming language just means that you can compute anything that can be computed using that language. In other words, it can be used to write arbitrary computations. You don't need much to achieve this; off the top of my head, I think that being able to read and write to storage, basic addition, conditionals and loops are enough. (Formally, it means that your language can be used to simulate a single-taped Turing machine.) A non-Turing-complete language is any language which does not have one of those capabilities. Because the bar is so low, most languages you have used in your life are Turing-complete. For example, you can imagine a simple calculator-like language for just writing mathematical expressions. It can do all basic math operations, has conditions, but no ability to repeat things (no loops or recursion). That language is not Turing-complete. You can trivially prove that programs from such a language will finish - they can't not! there's no ability to impede progress.

blackkitty 10y ago
You can actually have a turing complete instruction set with only one instruction. I am not sure as to the practicality but here is a wikipedia link to read. https://en.wikipedia.org/wiki/One_instruction_set_computer https://en.wikipedia.org/wiki/One_instruction_set_computer