2

While it takes a turing complete language to create any imaginable program, is it possible to compute most "useful" programs with a non-turing complete dynamically typed language? For example, is there a non-turing complete language capable of solving the Project Euler problems?

MaiaVictor
  • 5,830
  • @Telastyn you're right, but I've edited my question with something different. – MaiaVictor Aug 03 '13 at 23:34
  • Can you give me an example of a dynamic language that isn't turing complete so that I can solve some project Euler problems in it? I don't know how you count unix dc (it doesn't really have types), but the solution for problem 15 for a 4x4 grid is [d1-d1<F*]dsF8lFx4lFxd*/p –  Aug 04 '13 at 00:16
  • I don't know any. Also, what? – MaiaVictor Aug 04 '13 at 00:40
  • 1
    @Dokkat Lacking an example language, it is difficult to say if it is useful language or not. As to dc is a beautiful, terse, stack based language with macros (that one happens to be recursive). It may be turing complete, though I didn't begin to tap into that level of power in the language if it is. That was intentionally 'what'ed (I took out some whitespace that might otherwise enhance some of the readability and make the general solution more obvious), though it is a rather nice elegant solution. –  Aug 04 '13 at 00:54
  • @MichaelT I can't find any reference to it. – MaiaVictor Aug 04 '13 at 00:58
  • @Dokkat dc is a standard program on unix computers. (wikipedia page. –  Aug 04 '13 at 01:02
  • 2
    Why the requirement that it be dynamically typed? Is it actually important to the question, somehow? – Jake McArthur Aug 04 '13 at 03:07
  • @JakeMcArthur It's interesting, STLC and friends are non-turing complete useful static languages. But without types you can't have anything resembling functions.. Otherwise you could embed lambda calculus – daniel gratzer Aug 04 '13 at 03:42
  • 3
    The thing is: non-Turing-complete languages are usually designed for a specific purpose. Either they are DSLs, in which case they cannot (or at least shouldn't) be used to "compute most useful programs". Or, they are designed specifically because non-Turing-completeness allows powerful static analysis that is impossible in a Turing-complete language (e.g. Agda, Epigram, Coq, Guru, Charity) which means they necessarily have a powerful static type system. – Jörg W Mittag Aug 04 '13 at 11:50
  • An answer to the last question is going to depend a bit on what you mean by "solving" a project Euler question. In a number of cases (for instance, problem 17) a general solution would require looping, but if you limited yourself to the specific values in the question, you could unroll the loop. – Gort the Robot Aug 04 '13 at 15:22
  • @JörgWMittag that makes a lot of sense. – MaiaVictor Aug 04 '13 at 16:48
  • @JakeMcArthur the goal was to find the simplest non-turing complete language that is still powerful enough to solve common programming problems. I added the "dynamic" requisite because including a type system would probably make that theorical language not as simple as it could be. – MaiaVictor Aug 04 '13 at 16:50
  • @Dokkat As Jörg mentioned, there are a number of statically typed non-Turing-complete languages. The reason they aren't Turing complete is to aid the type system with certain proofs that aren't decidable in a Turing-complete language. If the "dynamic" bit wasn't actually a requirement, you should check out one of those. – KChaloux Aug 05 '13 at 14:16

0 Answers0