From this definition of Turing-completeness: https://en.wikipedia.org/wiki/Turing_completeness, why isn't Halide Turing-complete? The two conditions stated are that the language should have conditional branching (e.g. "if" and "goto") and that it should be able to change an arbitrary amount of memory (ignoring machine limitations). Yes it seems like Halide is a more limited language than other languages, but which condition specifically does it not satisfy?
jackcsullivan
Also what is an example of a recursive algorithm that does not have a bounded depth in the image grid setting?
tigreezy
Why is the domain scope of Halide constrained to 4D grids? Doesn't this really limit the use of the language or is it possible to make the language more versatile? I can see how it is useful for high performance image processing, but are there other applications?
Staffrishiu
In terms of the turing completeness question, I think one way to think of it is that if a language can implement every single program from a Turing complete language, then it is Turing complete. With that in mind, I think the fact that Halide only supports feed-foward pipelines and bounded depth recursion could mean that some things can't be implemented in Halide, making it not Turing complete.
Here's a link to Prof JRK's paper on halide, which is an interesting read if you'd like a much deeper dive into how the language works:
https://people.csail.mit.edu/jrk/halide-pldi13.pdf
From this definition of Turing-completeness: https://en.wikipedia.org/wiki/Turing_completeness, why isn't Halide Turing-complete? The two conditions stated are that the language should have conditional branching (e.g. "if" and "goto") and that it should be able to change an arbitrary amount of memory (ignoring machine limitations). Yes it seems like Halide is a more limited language than other languages, but which condition specifically does it not satisfy?
Also what is an example of a recursive algorithm that does not have a bounded depth in the image grid setting?
Why is the domain scope of Halide constrained to 4D grids? Doesn't this really limit the use of the language or is it possible to make the language more versatile? I can see how it is useful for high performance image processing, but are there other applications?
In terms of the turing completeness question, I think one way to think of it is that if a language can implement every single program from a Turing complete language, then it is Turing complete. With that in mind, I think the fact that Halide only supports feed-foward pipelines and bounded depth recursion could mean that some things can't be implemented in Halide, making it not Turing complete.
Apparently powerpoint is turing complete.
@tigreezy Halide can do more than 4D grids now