5 ms·

Eh, turing complete is a really low bar to clear. In practice it just means the compiler can't be proved to halt on valid code. Avoiding turing completeness re

Eh, turing complete is a really low bar to clear. In practice it just means the compiler can't be proved to halt on valid code. Avoiding turing completeness requires either very very careful design OR (trivially) a hard limit on size/iterations the compiler is allowed to make (a sufficiently small limit, obviously we call many things turing complete colloquially that have very low limits anyway like 8-bit cpus with ~kb of memory)

TeeWEE 10y ago
Turing complete is by now means a 'low bar'.. Turing complete means that a language, system can compute anything. Anything that can be computed, can be computed with java generics. Thats what it says. Its quite a important term.
- taeric 10y ago
  I believe the intent is that it is not a very informative bar to cross. Consider that Conway's Game of Life is Turing complete. Doesn't really increase the usage of it for solving problems. Basically, the expressiveness of a language is unrelated to it being Turing complete. And is much more relevant for most conversations.
- Avshalom 10y ago
  Basically all you need for turing completeness is the ability to jump/branch/ignore-some-bits on some criteria see SUBLEQ or cyclical tag systems or XY combinators. it's actually very hard to avoid in a system that is supposed to do some sort of computation.
- mikeash 10y ago
  It's a low bar in that it's easy to achieve. So easy that it's often done by accident, as is the case here and in many other cases (C++ templates are another example). It often takes more work to define a useful language not to be Turing complete.
naasking 10y ago
> In practice it just means the compiler can't be proved to halt on valid code. Which is a terrible outcome, and isn't a problem for nearly any other language save C++.
- gpderetta 10y ago
  Plenty of languages today have Turing complete type systems. I believe even Haskell with GHC extensions is.
  - curried_haskell 10y ago
    Scala's type system is also turing complete. They sometimes use type lambdas to get around some of the inexpressiveness of the type system.
amelius 10y ago
> Avoiding turing completeness Avoiding? Why would you want to avoid it? Guaranteeing that a compiler halts on any input is not something that is necessary in practice, and it restricts the amount of processing that can be done on the code during compilation.
- the8472 10y ago
  It very much is necessary. Take the linux kernel's eBPF interpreter for example. Since the code runs in kernel scope and in many critical places (system call interception, network processing) it's important that the code executes within a bounded amount of time. I think its restrictions are that it only allows forward jumps and a limited amount of instructions.
  - amelius 10y ago
    Regular expressions are not Turing complete, yet a regular expression can have exponential complexity. So the property "not Turing complete" does not give you anything practical. A better approach is to have a scheduler which is fair, and which gives the compiler the cycles it deserves, even if it needs many of them.
    - the8472 10y ago
      First, it's not about the time spent compiling. And also not a scheduling problem. Secondly, the eBPF constraints put the language even lower in the hierarchy than regular expressions.
      - andrewflnr 10y ago
        Even lower than "proper" regular expressions, i.e. guaranteed linear time?
        the8472 10y ago
        Yes, that's the intent. The code is executed inline when filtering packets, instrumenting system calls and to prefilter kernel probes for user space. It has to be really fast, i.e. execute in a bounded amount of time.
kens 10y ago
Accidental Turing completeness brings to mind the Zuse Z3 computer discussed recently. This 1941 system only supported fixed sequences without branching, but it was shown [1] to be Turing complete if you use weird tricks. The point is that it is fairly easy for systems to unexpectedly be Turing complete. On the other hand, the language built into Bitcoin [2] was deliberately designed not to be Turing complete. This avoids problems in deciding if a transaction is valid or not. [1] http://www.inf.fu-berlin.de/inst/ag-ki/rojas_home/documents/1997/Universal_Computer.pdf http://www.inf.fu-berlin.de/inst/ag-ki/rojas_home/documents/... [2] https://en.bitcoin.it/wiki/Script https://en.bitcoin.it/wiki/Script

TeeWEE 10y ago

Turing complete is by now means a 'low bar'.. Turing complete means that a language, system can compute anything. Anything that can be computed, can be computed with java generics. Thats what it says. Its quite a important term.

taeric 10y ago
I believe the intent is that it is not a very informative bar to cross. Consider that Conway's Game of Life is Turing complete. Doesn't really increase the usage of it for solving problems. Basically, the expressiveness of a language is unrelated to it being Turing complete. And is much more relevant for most conversations.
Avshalom 10y ago
Basically all you need for turing completeness is the ability to jump/branch/ignore-some-bits on some criteria see SUBLEQ or cyclical tag systems or XY combinators. it's actually very hard to avoid in a system that is supposed to do some sort of computation.
mikeash 10y ago
It's a low bar in that it's easy to achieve. So easy that it's often done by accident, as is the case here and in many other cases (C++ templates are another example). It often takes more work to define a useful language not to be Turing complete.

naasking 10y ago

> In practice it just means the compiler can't be proved to halt on valid code. Which is a terrible outcome, and isn't a problem for nearly any other language save C++.

gpderetta 10y ago
Plenty of languages today have Turing complete type systems. I believe even Haskell with GHC extensions is.
- curried_haskell 10y ago
  Scala's type system is also turing complete. They sometimes use type lambdas to get around some of the inexpressiveness of the type system.

amelius 10y ago

> Avoiding turing completeness Avoiding? Why would you want to avoid it? Guaranteeing that a compiler halts on any input is not something that is necessary in practice, and it restricts the amount of processing that can be done on the code during compilation.

the8472 10y ago
It very much is necessary. Take the linux kernel's eBPF interpreter for example. Since the code runs in kernel scope and in many critical places (system call interception, network processing) it's important that the code executes within a bounded amount of time. I think its restrictions are that it only allows forward jumps and a limited amount of instructions.
- amelius 10y ago
  Regular expressions are not Turing complete, yet a regular expression can have exponential complexity. So the property "not Turing complete" does not give you anything practical. A better approach is to have a scheduler which is fair, and which gives the compiler the cycles it deserves, even if it needs many of them.
  - the8472 10y ago
    First, it's not about the time spent compiling. And also not a scheduling problem. Secondly, the eBPF constraints put the language even lower in the hierarchy than regular expressions.
    - andrewflnr 10y ago
      Even lower than "proper" regular expressions, i.e. guaranteed linear time?
      - the8472 10y ago
        Yes, that's the intent. The code is executed inline when filtering packets, instrumenting system calls and to prefilter kernel probes for user space. It has to be really fast, i.e. execute in a bounded amount of time.

kens 10y ago

Accidental Turing completeness brings to mind the Zuse Z3 computer discussed recently. This 1941 system only supported fixed sequences without branching, but it was shown [1] to be Turing complete if you use weird tricks. The point is that it is fairly easy for systems to unexpectedly be Turing complete. On the other hand, the language built into Bitcoin [2] was deliberately designed not to be Turing complete. This avoids problems in deciding if a transaction is valid or not. [1] http://www.inf.fu-berlin.de/inst/ag-ki/rojas_home/documents/1997/Universal_Computer.pdf http://www.inf.fu-berlin.de/inst/ag-ki/rojas_home/documents/... [2] https://en.bitcoin.it/wiki/Script https://en.bitcoin.it/wiki/Script