[andoando]

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.

[svieira]

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

[andoando]

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.

[nonameiguess]

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.

[hot_gril]

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

[nferraz]

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

[shagie]

My favorite turning complete language is 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://news.ycombinator.com/item?id=35966537

https://softwareengineering.stackexchange.com/questions/2201...

https://web.archive.org/web/20150923211455/http://www.cs.vu....

[tossandthrow]

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]

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.

[tossandthrow]

> you need to build the physical computer

Exactly.

Now tell me how you will do unbound computation (ie. write on the n+1 cell in the Turing machine) with a fixed number og NAND gates and without a clock.

[hot_gril]

Oh, I see what you mean. Yeah it seems like you need a clock.

[reichstein]

NAND gates are enough to computer any boolean function. Being Turing complete requires some notion of state and state transition.

However, a RAM machine where the program counter is memory mapped, can be Turing complete with a [single machine instruction]( https://en.m.wikipedia.org/wiki/One-instruction_set_computer).

[andoando]

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.

[thequux]

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.