5 ms·

I'm not convinced that Turing completeness is needed for real functionality. Can you name a "practical" function that is computable but not primitive recursive?

by Grue3 8y ago

I'm not convinced that Turing completeness is needed for real functionality. Can you name a "practical" function that is computable but not primitive recursive? Just because you can theoretically compute Ackermann function doesn't mean it has anything but academic interest.

dahart 8y ago
Are you kidding? All you need for TC is conditional repetition, you don't need recursion. Loops & variables are the two things that make a language Turing complete. Almost everything interesting in the computing world is done using conditional loops. To use your Animstack project as an example, you're not allowing your users to write things like Perlin turbulence (multiple octaves of noise) without a loop, or custom convolutions, or a Mandelbrot fractal, or 2d fluid flow. There are all kinds of practical and fun things you're artificially restricting yourself from. Some of those things can be technically done without TC, but none typically are because it's inconvenient, and because TC doesn't cause any practical problems. Other examples that use Turing completeness in practice: UI event loops (all videogames, all of robotics, all servers of any kind), string replacement, sorting a list of arbitrary size, searching a list of arbitrary size, path tracing renderers, file i/o, regression and any non-linear optimization, I could go on for a very long time, the list is really long. I'd like to know what interesting things you think you can do without conditional loops in a convenient way. Not what's theoretically possible if you bend over backwards, but what's practical and easy. I feel like the list is pretty short. You also didn't answer the question. What is a real problem with TC? Killing runaway programs & infinite loops is not a problem in practice, and therefore neither is preventing people from writing infinite loops. So what's a problem with TC that I should care about? You can never guarantee people won't make mistakes, unless you make all their decisions for them. That's what non-TC languages normally feel like; a recipe book for pre-decided outcomes, not very powerful, not very interesting. Nor did you address the fact that a decidable non-TC language doesn't guarantee halting in any reasonable amount of time. So how is it actually helping you to prevent TC? It doesn't seem like it is. Here's a question- how many conditional loops did you use in the implementation of Animstack, under the hood?
- Grue3 8y ago
  >Other examples that use Turing completeness in practice: UI event loops (all videogames, all of robotics, all servers of any kind), string replacement, sorting a list of arbitrary size, searching a list of arbitrary size, path tracing renderers, file i/o, regression and any non-linear optimization, I could go on for a very long time, the list is really long. A lot of these don't require Turing completeness. Anything that can be given runtime guarantee that's O(n^k) or even O(e^n) can be implemented without Turing completeness. Now if you need O(Ackerman-function) runtime, you gotta bring out the Turing machine, but I don't think such algorithms exist in practice. Consider that pure SQL is not Turing complete. You can "search lists of arbitrary size" in it. And you can construct pretty complex queries in it to do so. It's the most popular programming language around and most people don't use the parts that make it Turing complete. >Almost everything interesting in the computing world is done using conditional loops. There's almost nothing that requires conditional loops with arbitrary conditions. Loops in Python all have the form "for element in sequence" and you can go pretty far without using custom iterators that allow for infinite sequences, which is considered an advanced topic. A lot of people program in non-Turing complete subset of Python! > how many conditional loops did you use in the implementation of Animstack, under the hood? I actually can answer this easily. It's implemented in TinyScheme (the scripting language of GIMP) which doesn't have loops, only recursion. So technically zero. Scheme is Turing-complete of course, but I don't think it has to be to implement Animstack.
  - dahart 8y ago
    Recursion is looping, so technically not zero, right? There’s a lot of ignoring practice in your response. Python, C, O(n^k) algorithms, all of it is implemented with Turing Complete languages, whether it’s technically required or not. I don’t know the non-TC subset of Python you’re talking about, nor how many people are using it. Are they using it specifically to limit themselves to less powerful constructs, or for other reasons? The web says SQL is in fact TC contrary to your claim. https://stackoverflow.com/questions/900055/is-sql-or-even-tsql-turing-complete https://stackoverflow.com/questions/900055/is-sql-or-even-ts... > There's almost nothing that requires conditional loops with arbitrary conditions. The entire stack of tech you are using to type that sentence and send it over to Hacker news runs on intentionally infinite loops. The input element, the js in your browser, the event loop in your browser, your NIC and WiFi box, all the routers between you and HN, the web server responding to news.ycombinator.com. GIMP has an infinite loop waiting for user commands to launch your Animstack scripts. My professional field is graphics, which is why I mentioned path tracing, and path tracing requires loops with arbitrary conditions, as do many statistical simulations. How would you write a non-TC memory manager? I don’t really know what you have in mind when you say almost nothing requires conditional loops, but I don’t see a lot of evidence of that being true. All video games run on while(1) loops. You still didn’t answer my questions, so maybe this is as far as we need to go. Why does TC matter at all when you can kill a script? What is preventing TC buying your language when the programs are bug free? What is non-TC buying you when non-TC programs can take aribtrary amounts of time? Why is restricting the power of a language desirable? I havent seen a single reason yet that I buy.

Grue3 8y ago
>The web says SQL is in fact TC contrary to your claim. Did you even read the link? You need extensions to make SQL Turing complete. Your replies indicate to me you lack the necessary theoretical background to discuss Turing completeness, since pure SQL not being TC is such a basic fact you don't need to look it up on the web. The fact that the entire tech stack is TC is not a proof that TC is needed for individual parts of the tech stack. Indeed, some of the components of the web stack, namely CSS, are not TC (no, please don't look it up on the web and come back with "CSS is turing complete" bullshit, they're clearly wrong because halting problem of CSS is decidable). By the way Turing machine doesn't involve human interaction, so all your examples that involve interactivity (UI loops) are outside of scope of this discussion. >What is preventing TC buying your language when the programs are bug free? There's no such thing as bug free program. When you need to execute arbitrary programs, not being TC buys you a lot of guarantees that can be useful.
- dahart 8y ago
  > When you need to execute arbitrary programs, not being TC buys you a lot of guarantees that can be useful. Please, elaborate! What are these useful guarantees? Can you name some? > Did you even read the link? I think so... the first sentence says you don’t need an extension. The linked Mandelbrot set example is “SQL:2008 conformant” and depends on “nothing”. https://wiki.postgresql.org/wiki/Mandelbrot_set https://wiki.postgresql.org/wiki/Mandelbrot_set Is that using an extension? > By the way Turing machine doesn’t involve human interaction, so all your examples that involve interactivity (UI loops) are outside of scope of this discussion. Okay, so Turing completeness doesn’t apply to GIMP or Animstack at all, right? That’s what I was trying to suggest before. ;) Your own stated reason for removing TC from Animstack was UI. Who says human input doesn’t apply? Alan Turing didn’t say that. Wikipedia says that interaction does apply: https://en.m.wikipedia.org/wiki/Turing_machine#Interaction https://en.m.wikipedia.org/wiki/Turing_machine#Interaction “In principle, it is possible to model this [interaction] by having an external agent read from the tape and write to it at the same time as a Turing machine...” > The fact that the entire stack is TC is not a proof that TC is needed No, it’s just proof that TC languages are common and useful, and that not many practitioners would agree that TC is a “bad thing”. > Indeed, some of the components of the web stack, namely CSS, are not TC So? What does it prove if a few parts are non TC, when so many of them are? CSS is for styling, not for writing programs, unlike Animstack and sed and the other examples you’ve been using. It tends to undermine your points a little bit to hold up CSS as an example of a non-TC language. I wouldn’t want to use CSS to compute things, so I don’t care if it’s Turing complete or not. For that matter, I don’t care whether any language is Turing complete, as long as I can get my work done easily, why should I? > no, please don’t look it up on the web Okay, I won’t. Just kidding, here’s the answer, not just a claim, but an implementation of Turing Completeness. So what’s clearly wrong about it? https://stackoverflow.com/a/5239256 https://stackoverflow.com/a/5239256 To be honest, I don’t care what’s wrong with it. Or with sed or any other language. Not in purist academic theory. I wanted to hear if there are practical reasons to care, but since you won’t answer and I haven’t heard any, then I don’t care.