Is a language whose only ability to affect state comes from calling other languages Turing-complete?

Question

This may be an exercise in semantics, but I'm genuinely split on whether or to consider something to be Turing-complete, and would like some help in thinking through the problem.

Say there's a language that has three commands:

• Run external program with arguments, storing the results somewhere
• Loop back to arbitrary line in the program
• Branch

where "branch" operation checks the state generated by an external command, and where the arguments to external programs come only from an initial state the user specifies, or the output of 'upstream' commands; can you say the language itself is Turing-complete?

My issue comes in that the language itself, in allowing you to only specify the starting values, does not have a "modify the state" command; in order for any state to be modified, an external program must be called. If you were to try to write a program in this language without calling something external, you couldn't do it; however, since the language has the concept of calling external languages built-in (and that's its main purpose), it can act Turing-complete in practice.

It's as if bash could only loop, call and store results from external programs, and make decisions on the values stored. Would it then be Turing-complete?

Thanks!

Answer 1

So with language you mean a programming language, not a formal language, right? I answer in as little technical detail as your defintions ;-)

For a computation with input i with branches you can protocol all the lines to which the branches jump in a sequence like 55,100,7,67. Now replace all branches by calls to a program p that returns the corresponding line number:

p(i,1)=55, p(i,2)=100...

In the following line you jump to the line number returned by the program. You should compute the same result as the initial program. We do not even need the full power of "branch".

Such a program p exists for every computable function. So for every function there exists also has an equivalent one without explicit branches.

The question whether your programming language alone would be Turing-complete: without the external calls it cannot even add, does not have access to memory or anything, as far as you have specified it. I have supposed some elemental abilities for my answer. But to answer your question, these details are decisive. Just with your GOTO and register increment there might be ways to do branches implicitly.