9 ms·

Very cool. Someone correct me if I am wrong but I dont think this is accurate. >Minimally, should have the following features: variables, looping (think: for/w

Very cool. Someone correct me if I am wrong but I dont think this is accurate. >Minimally, should have the following features: variables, looping (think: for/while loops), conditional branching (think: if/else statements) and some form of recursion (think: functions). Why? These are what make a programming language Turing-complete.

hot_gril 2y ago
On the practical side, I can think of one Turing-complete language people actually use that doesn't have loops or variables: Erlang.
svieira 2y ago
Either an infinite for/while and if or unbounded recursion are necessary but you don't need both for Turing completeness. [1]: https://en.wikipedia.org/wiki/Turing_completeness#Examples https://en.wikipedia.org/wiki/Turing_completeness#Examples
- andoando 2y ago
  My understanding is theyre two sides of the same coin. Any loop can be written recurisvely or iteratively. And a loop is really just a move to the same instruction, or equivalently a replication of the same instruction.
thequux 2y ago
Either conditional looping (like the for loop in C) or recursion is enough for Turing completeness. Practically speaking, conditional looping generally requires mutable variable bindings, but I can imagine a SSA-based language where variables are unnecessary. With recursion, you have no need for mutability as the function call primitive gives you the variable rebinding you need.
nferraz 2y ago
In fact, NAND gates are enough to build a Turing complete machine. ;-)
- shagie 2y ago
  My favorite turning complete language is Fractran - https://en.wikipedia.org/wiki/FRACTRAN https://en.wikipedia.org/wiki/FRACTRAN 17 78 19 23 29 77 95 77 1 11 13 15 1 55 -- -- -- -- -- -- -- -- -- -- -- -- -- -- 91 85 51 38 33 29 23 19 17 13 11 2 7 1 That computes prime numbers. Iterate through the list (start with n = 2) and iterate through until the fraction is an integer. Repeat with the new number. For this, after 2, the next value is 15 (when it gets to 15/2). Then it will be 825 (15 * 55/1). Then it will be 725 (825 * 29 / 33) and so on. At some point, n will be 2^x where the sequence of when the number is just a power of 2 will be: 2^2, 2^3, 2^5, 2^7, 2^11 and so on... the exponents of 2 are the prime sequence. 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4, 30 ... https://oeis.org/A007542 https://oeis.org/A007542 https://news.ycombinator.com/item?id=35966537 https://news.ycombinator.com/item?id=35966537 https://softwareengineering.stackexchange.com/questions/220188/why-is-fractran-turing-complete https://softwareengineering.stackexchange.com/questions/2201... https://web.archive.org/web/20150923211455/http://www.cs.vu.nl/~diem/publications/slides/fractran-2011-05-31.pdf https://web.archive.org/web/20150923211455/http://www.cs.vu....
- andoando 2y ago
  While true, to build a language using NAND gates, the language has to specify how to assemble those gates, which will still require conditionals and loops if you want it to build any machine.
- tossandthrow 2y ago
  How will you do unbound computation with only NAND gates? Either you need a clock (not a NAND gate) or you need to implement a clock using NAND gates, but that assumes physical aspects such as power propagation speed. Typically you say that you can make arbitrary functions between any two closed domains using only NAND gates.
  - hot_gril 2y ago
    Turing completeness isn't about having everything you need to build the physical computer, just about expressing program logic that can perform a certain class of unbounded computations. Like, given any C program's logic that takes some input and gives an output, you could calculate the same thing (painfully) with NAND gates. Anyway, bringing up Turing completeness is overly theoretical when talking about a programming language. It's pretty hard to make a language not Turing-complete, and it doesn't say much about what you can use it for IRL.
nonameiguess 2y ago
Trivially, you can get Turing completeness out of a Turing machine, which does not have these features, so no, it is not accurate to say they're absolutely necessary. There's a practical side to this, though. What sort of syntactic conveniences should you provide such that anyone might actually want to use your language? That's probably what it should say. The mov instruction is Turing complete, but you likely want some higher level of abstraction that allows for things like developer ergonomics, the possibility of type checking, allowing for human readable source code.
- deleted 2y ago
  [deleted]
- deleted 2y ago
  [deleted]

hot_gril 2y ago

On the practical side, I can think of one Turing-complete language people actually use that doesn't have loops or variables: Erlang.

svieira 2y ago

Either an infinite for/while and if or unbounded recursion are necessary but you don't need both for Turing completeness. [1]: https://en.wikipedia.org/wiki/Turing_completeness#Examples https://en.wikipedia.org/wiki/Turing_completeness#Examples

andoando 2y ago
My understanding is theyre two sides of the same coin. Any loop can be written recurisvely or iteratively. And a loop is really just a move to the same instruction, or equivalently a replication of the same instruction.

thequux 2y ago

Either conditional looping (like the for loop in C) or recursion is enough for Turing completeness. Practically speaking, conditional looping generally requires mutable variable bindings, but I can imagine a SSA-based language where variables are unnecessary. With recursion, you have no need for mutability as the function call primitive gives you the variable rebinding you need.

nferraz 2y ago

In fact, NAND gates are enough to build a Turing complete machine. ;-)

shagie 2y ago
My favorite turning complete language is Fractran - https://en.wikipedia.org/wiki/FRACTRAN https://en.wikipedia.org/wiki/FRACTRAN 17 78 19 23 29 77 95 77 1 11 13 15 1 55 -- -- -- -- -- -- -- -- -- -- -- -- -- -- 91 85 51 38 33 29 23 19 17 13 11 2 7 1 That computes prime numbers. Iterate through the list (start with n = 2) and iterate through until the fraction is an integer. Repeat with the new number. For this, after 2, the next value is 15 (when it gets to 15/2). Then it will be 825 (15 * 55/1). Then it will be 725 (825 * 29 / 33) and so on. At some point, n will be 2^x where the sequence of when the number is just a power of 2 will be: 2^2, 2^3, 2^5, 2^7, 2^11 and so on... the exponents of 2 are the prime sequence. 2, 15, 825, 725, 1925, 2275, 425, 390, 330, 290, 770, 910, 170, 156, 132, 116, 308, 364, 68, 4, 30 ... https://oeis.org/A007542 https://oeis.org/A007542 https://news.ycombinator.com/item?id=35966537 https://news.ycombinator.com/item?id=35966537 https://softwareengineering.stackexchange.com/questions/220188/why-is-fractran-turing-complete https://softwareengineering.stackexchange.com/questions/2201... https://web.archive.org/web/20150923211455/http://www.cs.vu.nl/~diem/publications/slides/fractran-2011-05-31.pdf https://web.archive.org/web/20150923211455/http://www.cs.vu....
andoando 2y ago
While true, to build a language using NAND gates, the language has to specify how to assemble those gates, which will still require conditionals and loops if you want it to build any machine.
tossandthrow 2y ago
How will you do unbound computation with only NAND gates? Either you need a clock (not a NAND gate) or you need to implement a clock using NAND gates, but that assumes physical aspects such as power propagation speed. Typically you say that you can make arbitrary functions between any two closed domains using only NAND gates.
- hot_gril 2y ago
  Turing completeness isn't about having everything you need to build the physical computer, just about expressing program logic that can perform a certain class of unbounded computations. Like, given any C program's logic that takes some input and gives an output, you could calculate the same thing (painfully) with NAND gates. Anyway, bringing up Turing completeness is overly theoretical when talking about a programming language. It's pretty hard to make a language not Turing-complete, and it doesn't say much about what you can use it for IRL.

nonameiguess 2y ago

Trivially, you can get Turing completeness out of a Turing machine, which does not have these features, so no, it is not accurate to say they're absolutely necessary. There's a practical side to this, though. What sort of syntactic conveniences should you provide such that anyone might actually want to use your language? That's probably what it should say. The mov instruction is Turing complete, but you likely want some higher level of abstraction that allows for things like developer ergonomics, the possibility of type checking, allowing for human readable source code.

deleted 2y ago
[deleted]
deleted 2y ago
[deleted]