5 ms·

Are node-based VPLs like Houdini Turing-complete? I've only used Grasshopper, but the sense I got was that it was not Turing-complete. If they're not Turing-com

Are node-based VPLs like Houdini Turing-complete? I've only used Grasshopper, but the sense I got was that it was not Turing-complete. If they're not Turing-complete, then I don't think "programming" is the right word. Computer-aided design would be more appropriate.

ModernMech 5y ago
Why does Turing completeness discriminate an activity between CAD and programming? So when one writes CSS or Makefiles they are programming; but if they write systems in e.g Datalog they are doing CAD?
- simulate-me 5y ago
  CSS is a great example. Someone who only engages with CSS and HTML would best be described as a web designer.
  - fiddlerwoaroof 5y ago
    CSS + HTML is Turing complete: https://lemire.me/blog/2011/03/08/breaking-news-htmlcss-is-turing-complete/ https://lemire.me/blog/2011/03/08/breaking-news-htmlcss-is-t...
    - fiddlerwoaroof 5y ago
      On the other hand, ACL2 isn’t Turing complete but can express many interesting programs: https://www.cs.utexas.edu/users/moore/acl2/v8-4/combined-manual/index.html?topic=ACL2____TUTORIAL1-TOWERS-OF-HANOI https://www.cs.utexas.edu/users/moore/acl2/v8-4/combined-man...
      - simulate-me 5y ago
        Are you sure ACL2 isn't Turing complete? I can't seem to find a proof of this.
        fiddlerwoaroof 5y ago
        It’s embedded in a Turing complete language, but you can’t prove theorems about programs written in a Turing-complete language (Rice’s Theorem) so the ACL2 language itself has to be limited to programs that can be determined to halt. The J-Bob language from the book The Little Prover might be a better example. There’s a whole programming paradigm here of languages that aren’t Turing complete: https://en.m.wikipedia.org/wiki/Total_functional_programming https://en.m.wikipedia.org/wiki/Total_functional_programming
    - simulate-me 5y ago
      Whether or not it's Turing-complete is not all that important. The important part is whether or not Turing-completeness is required for what is being created. In the case of HTML and CSS, Turing-completeness is almost always not a requirement.
      - chowells 5y ago
        Turing completeness is not a requirement for any computational task that is guaranteed to complete, either. You only need it to add infinite loop bugs. Just to be clear - the things you actually care about expressing in a program don't require Turing completeness about 99.99999% of the time. The main exceptions are things like unbounded searches where the code will only terminate if it finds a solution to something, and there's no a priori size bound on the solution space. We use Turing complete languages as a compromise. Proving your algorithm terminates to the satisfaction of a proof checker is often more work than it's worth. We've decided allowing bugs that a termination checker would prevent is less work to deal with than satisfying a termination checker. But for my daily work, Turing completeness is a practical compromise, not a necessity for expressing the algorithms I need to.
- doliveira 5y ago
  > when one writes CSS or Makefiles they are programming They're not? At least that's not how I see it being called
  - Someone 5y ago
    For GNU make, it depends on the makefile. https://okmij.org/ftp/Computation/#Makefile-functional https://okmij.org/ftp/Computation/#Makefile-functional: The language of GNU make is indeed functional, complete with combinators (map and filter), applications and anonymous abstractions. Yes, GNU make supports lambda-abstractions. The following is one example from the Makefile in question: it is a rule to build a test target for the SCM Scheme system. The list of source code files and the name of the target/root-test-file are passed as two arguments of the rule: make-scmi= scm -b -l $(LIBDIR)/myenv-scm.scm \ $(foreach file,$(1),-l $(LIBDIR)/$(file)) \ -l $(2).scm The rule returns the OS command to interpret or compile the target. It is to be invoked as $(call make-scmi,util.scm catch-error.scm,vmyenv) As in TeX, the arguments of a function are numbered (it is possible to assign them meaningful symbolic names, too). Makefile's foreach corresponds to Scheme's map. The comparison with the corresponding Scheme code is striking: (define make-scmi (lambda (arg1 arg2) `(scm -b -l ,(mks LIBDIR '/ 'myenv-scm.scm) ,@(map (lambda (file) `(-l ,(mks LIBDIR '/ file))) arg1) -l ,(mks arg2 '.scm)))) (via https://stackoverflow.com/a/3480982 https://stackoverflow.com/a/3480982, which gives a Fibonacci example)
pfortuny 5y ago
Are finite state automata turing complete? No. But any normal person would say that programming them is indeed programming.
- simulate-me 5y ago
  Creating something Turing-incomplete is not the same thing as using something not Turing-incomplete. For instance, the people who created Houdini are programmers. The people who use Houdini are not. I can program a dishwasher using a FSA, but that doesn’t make people who use dishwashers programmers.
jcelerier 5y ago
The one I work on, https://ossia.io https://ossia.io has ways to express loops and conditions in its visual syntax, which can get pretty close.
- andybak 5y ago
  Ossia looks really interesting - I've wondered for years how the "timeline vs node graph" distinction could be erased. Who uses it on the whole? How big is the community? (I'm a developer on Open Brush https://openbrush.app/ https://openbrush.app/ and I'm really interested in hearing how other open source creative tools do things)
  - jcelerier 5y ago
    :) thanks ! > Who uses it on the whole? it mainly targets media artists. here's a few shows / installations / artworks that used it : https://ossia.io/gallery.html https://ossia.io/gallery.html > How big is the community? not super big aha, it's a fairly specific niche: people who got dissatisfied with e.g. Max, etc. and needed some form of timeline.
jayd16 5y ago
I guess I don't know for sure but I think Houdini is Turing complete. You can read, write, and branch on arbitrary data. Shader graphs support loops which should imply they're Turing complete as well?
erichocean 5y ago
> Are node-based VPLs like Houdini Turing-complete? As a Houdini user and 20+ year professional software developer… Yes, Houdini's node-based VPL is Turing-complete.

ModernMech 5y ago

Why does Turing completeness discriminate an activity between CAD and programming? So when one writes CSS or Makefiles they are programming; but if they write systems in e.g Datalog they are doing CAD?

simulate-me 5y ago
CSS is a great example. Someone who only engages with CSS and HTML would best be described as a web designer.
- fiddlerwoaroof 5y ago
  CSS + HTML is Turing complete: https://lemire.me/blog/2011/03/08/breaking-news-htmlcss-is-turing-complete/ https://lemire.me/blog/2011/03/08/breaking-news-htmlcss-is-t...
  - fiddlerwoaroof 5y ago
    On the other hand, ACL2 isn’t Turing complete but can express many interesting programs: https://www.cs.utexas.edu/users/moore/acl2/v8-4/combined-manual/index.html?topic=ACL2____TUTORIAL1-TOWERS-OF-HANOI https://www.cs.utexas.edu/users/moore/acl2/v8-4/combined-man...
    - simulate-me 5y ago
      Are you sure ACL2 isn't Turing complete? I can't seem to find a proof of this.
      - fiddlerwoaroof 5y ago
        It’s embedded in a Turing complete language, but you can’t prove theorems about programs written in a Turing-complete language (Rice’s Theorem) so the ACL2 language itself has to be limited to programs that can be determined to halt. The J-Bob language from the book The Little Prover might be a better example. There’s a whole programming paradigm here of languages that aren’t Turing complete: https://en.m.wikipedia.org/wiki/Total_functional_programming https://en.m.wikipedia.org/wiki/Total_functional_programming
  - simulate-me 5y ago
    Whether or not it's Turing-complete is not all that important. The important part is whether or not Turing-completeness is required for what is being created. In the case of HTML and CSS, Turing-completeness is almost always not a requirement.
    - chowells 5y ago
      Turing completeness is not a requirement for any computational task that is guaranteed to complete, either. You only need it to add infinite loop bugs. Just to be clear - the things you actually care about expressing in a program don't require Turing completeness about 99.99999% of the time. The main exceptions are things like unbounded searches where the code will only terminate if it finds a solution to something, and there's no a priori size bound on the solution space. We use Turing complete languages as a compromise. Proving your algorithm terminates to the satisfaction of a proof checker is often more work than it's worth. We've decided allowing bugs that a termination checker would prevent is less work to deal with than satisfying a termination checker. But for my daily work, Turing completeness is a practical compromise, not a necessity for expressing the algorithms I need to.
doliveira 5y ago
> when one writes CSS or Makefiles they are programming They're not? At least that's not how I see it being called
- Someone 5y ago
  For GNU make, it depends on the makefile. https://okmij.org/ftp/Computation/#Makefile-functional https://okmij.org/ftp/Computation/#Makefile-functional: The language of GNU make is indeed functional, complete with combinators (map and filter), applications and anonymous abstractions. Yes, GNU make supports lambda-abstractions. The following is one example from the Makefile in question: it is a rule to build a test target for the SCM Scheme system. The list of source code files and the name of the target/root-test-file are passed as two arguments of the rule: make-scmi= scm -b -l $(LIBDIR)/myenv-scm.scm \ $(foreach file,$(1),-l $(LIBDIR)/$(file)) \ -l $(2).scm The rule returns the OS command to interpret or compile the target. It is to be invoked as $(call make-scmi,util.scm catch-error.scm,vmyenv) As in TeX, the arguments of a function are numbered (it is possible to assign them meaningful symbolic names, too). Makefile's foreach corresponds to Scheme's map. The comparison with the corresponding Scheme code is striking: (define make-scmi (lambda (arg1 arg2) `(scm -b -l ,(mks LIBDIR '/ 'myenv-scm.scm) ,@(map (lambda (file) `(-l ,(mks LIBDIR '/ file))) arg1) -l ,(mks arg2 '.scm)))) (via https://stackoverflow.com/a/3480982 https://stackoverflow.com/a/3480982, which gives a Fibonacci example)

pfortuny 5y ago

Are finite state automata turing complete? No. But any normal person would say that programming them is indeed programming.

simulate-me 5y ago
Creating something Turing-incomplete is not the same thing as using something not Turing-incomplete. For instance, the people who created Houdini are programmers. The people who use Houdini are not. I can program a dishwasher using a FSA, but that doesn’t make people who use dishwashers programmers.

jcelerier 5y ago

The one I work on, https://ossia.io https://ossia.io has ways to express loops and conditions in its visual syntax, which can get pretty close.

andybak 5y ago
Ossia looks really interesting - I've wondered for years how the "timeline vs node graph" distinction could be erased. Who uses it on the whole? How big is the community? (I'm a developer on Open Brush https://openbrush.app/ https://openbrush.app/ and I'm really interested in hearing how other open source creative tools do things)
- jcelerier 5y ago
  :) thanks ! > Who uses it on the whole? it mainly targets media artists. here's a few shows / installations / artworks that used it : https://ossia.io/gallery.html https://ossia.io/gallery.html > How big is the community? not super big aha, it's a fairly specific niche: people who got dissatisfied with e.g. Max, etc. and needed some form of timeline.

jayd16 5y ago

I guess I don't know for sure but I think Houdini is Turing complete. You can read, write, and branch on arbitrary data. Shader graphs support loops which should imply they're Turing complete as well?

erichocean 5y ago

> Are node-based VPLs like Houdini Turing-complete? As a Houdini user and 20+ year professional software developer… Yes, Houdini's node-based VPL is Turing-complete.