Hacker News Reader

Comment by simulate-me | Hacker News Reader

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.

View on HN

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

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/ and I'm really interested in hearing how other open source creative tools do things)

:) 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

> 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.

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

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.

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?

> 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.

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?

CSS is a great example. Someone who only engages with CSS and HTML would best be described as a web designer.

CSS + HTML is Turing complete:

https://lemire.me/blog/2011/03/08/breaking-news-htmlcss-is-t...

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-man...

Are you sure ACL2 isn't Turing complete? I can't seem to find a proof of this.

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

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.

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.

> when one writes CSS or Makefiles they are programming

They're not? At least that's not how I see it being called

For GNU make, it depends on the makefile. 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, which gives a Fibonacci example)

Reply on news.ycombinator.com