Why are some programming languages Turing complete but lack some abilities of other languages?

Question

I came across an odd problem when writing an interpreter that (should) hooks to external programs/functions: Functions in 'C' and 'C++' can't hook variadic functions, e.g. I can't make a function that calls 'printf' with the exact same arguments that it got, and instead has to call an alternate version that take a variadic object. This is very problematic since I want to be able to make an object that hold an anonymous hook.

So, I thought that this was weird since Forth, JavaScript, and perhaps a plethora of other languages can do this very easily without having to resort to assembly language/machine code. Since other languages can do this so easily, does that mean that the class of problems that each programming language can solve actually varies by language, even though these languages are all Turing complete?

Answer 1

Turing complete languages can compute the same set of functions $\mathbb{N}^k \rightarrow \mathbb{N}$, which is the set of general recursive partial functions. That's it.

This says nothing about the language features. A Turing Machine has very limited compositional features. The untyped $\lambda$-calculus is far more compositional, but lacks many features commonly found in modern languages.

Turing completeness tells nothing about having types, built in arrays/integers/dictionaries, input/output capabilities, network access, multithreading, dynamic allocation, ...

Just because Java does not have feature X (say, macros, higher-rank types, or dependent types), it does not suddenly stop being Turing complete.

Turing completeness and language expressiveness are two different notions.

Answer 2

Turing completeness is an abstract concept of computability. If a language is Turing complete, then it is capable of doing any computation that any other Turing complete language can do.

This does not, however, say how convenient it is to do so. Some features that are easy in some languages may be very difficult in others, due to design choices. Turing completeness just says that you can do the computation. As an extreme example, it may be difficult to hook varadic functions in C++, but it is possible to write a JavaScript interpreter in C++ which can hook variadic functions.

Language design is a pretty interesting art. One of the major steps one has to undertake is identifying which behaviors you want to form the backbone of your language. These behaviors are things that are easy to do in your language because they're built into the ground floor. We make design decisions about which features to include in every language.

As to your particular example, when C was developed, it was designed to operate very close to the way the assembly languages of the day operated. Variadic functions simply pushed arguments onto the stack, with very little typesafety. The implementation of these variadic functions was left to the compiler, to ensure maximum portability. Accordingly, very few assumptions were made about the capabilities of the hardware. By the time JavaScript came along, the scene had changed. It already operates in a virtual machine as an interpreted language, so the balance shifts towards convenience. Permitting hooking of variadic functions becomes reasonable. Even in the case of JavaScript that is Just In Time Compiled, our compilers are willing to store far more extra information about the arguments than the C compilers of yore were willing to store.

Answer 3

Think of programming languages as different land vehicles: bicycles, cars, hovercars, trains.

Turing Completeness says "this vehicle can go anywhere any other vehicle can go." That is, you can compute all the same functions. Input to output, start to end.

But, that statement says nothing about how you get there. It might be on rails, it might be on roads, it might be in the air. In the same way, Turing Completeness says nothing about how you compute a function. You might use recursion, or iteration, or some weird cellular automata. You might use types or not, you might use dynamic or static techniques. But, if all you consider is functions (or sets/formal languages) you can compute, as long as you are Turing Complete, these features give you the same power.

Answer 4

What you are essentially asking about is the difference between the computational power and what is commonly called the expressive power (or just expressiveness) of a language (or system of computation).

Computational Power

The computational power refers to what kinds of problems the language can compute. The most well-known class of computational power is that which is equivalent to a Universal Turing Machine. There are a lot of other systems of computation, such as Random Access Machines, λ-calculus, SK combinator calculus, µ-recursive functions, WHILE programs, and many others. And as it turns out, all of these can simulate each other, which means that they all have the same computational power.

This gives rise to the Church-Turing Thesis (named after Alonzo Church who created the λ-calculus and Alan Turing who created the Universal Turing Machine). The Church-Turing-Thesis is a hypothesis on computability with two aspects:

1. all computing systems capable of general computation are equally powerful, and
2. a human being following an algorithm can compute exactly the functions that a Turing Machine (and thus any of the other systems) can compute.

The second is more important in the field of philosophy of mind than computer science, though.

However, there are two things the Church-Turing-Thesis doesn't say, that are very relevant to your question:

1. how efficient the various simulations are and
2. how convenient the encoding of a problem is.

A simple example for (1): on a Random Access Machine, copying an array takes time proportional to the length of the array. On a Turing Machine, however, it takes time proportional to the square of the length of the array, because the Turing Machine does not have random memory access, it can only move across the tape one cell at a time. Therefore, it needs to move across the n elements of the array n times to copy them. So, different models of computation may have different performance characteristics, even in the asymptotic case, where we try to abstract away from implementation details.

Examples for (2) abound: both λ-calculus and Python are Turing-complete. But would you rather write a program in Python or in λ-calculus?

There is also a third wrinkle I have skirted around until now: all of those original systems were designed by logicians, philosophers, or mathematicians, not by computer scientists … simply because computers and thus computer science didn't exist. These all go back to the early 1930s, even before Konrad Zuse's very first experiments (which weren't programmable and/or Turing-complete anyway). They only talk about "computable functions on the natural numbers".

Now, as it turns out, there's a lot you can express as functions on natural numbers – after all, our modern computers even get by with a lot less than that (basically 3-4 functions on the numbers 0 and 1, and that's it), but, for example, what function does an operating system compute?

This notion of I/O, side-effects, interacting with the environment, is not captured by the idea of "functions over natural numbers". And yet, it is kind of important, since, as Simon Peyton Jones once put it "All a pure function with no side-effects does, is make your CPU hot", to which an audience member replied "actually, that is a side-effect, too!"

Edwin Brady, the designer of Idris, (only half) jokingly uses (I don't know whether he invented it) the term "Tetris-complete" to express this difference between "can compute any computable function on natural numbers" and "can be used to write non-trivial programs that interact with the environment". Even more ironically, he demonstrates this by having an implementation of a Space Invaders clone in Idris, but he says that he is confident that Tetris reduces to Space Invaders.

Another thing to point out is that not only is Turing-equivalence not necessarily enough to talk about actually writing "useful" programs, it may OTOH also not even be necesssary. E.g. SQL has only become Turing-equivalent with ANSI SQL:1999, but it was still useful before that. In fact, some might argue that making it Turing-equivalent hasn't added to its usefulness at all. There are many Domain-Specific Languages that aren't Turing-equivalent. Data Description Language typically aren't (and shouldn't be). Total Languages obviously can't be Turing-equivalent, yet you can still write event loops, web servers, or operating systems in them. There are also languages which are Turing-equivalent but where this is actually considered to be a mistake.

So, all in all, Turing-equivalence is not terribly interesting, unless you want to statically analyze programs.

Expressiveness

Assuming that our computation system is computationally powerful enough to even solve our problem at all, what we have to do next, is to express our algorithm for solving that problem in some sort of formal notation for that system. In other words: we need to write a program in some computer language. That's where the notion of expressiveness comes in.

It refers to, essentially, how "easy" or "enjoyable" it is to write our program in our particular programming language. As you can see, the notion is quite vague, subjective, and more psychological than technical.

However, there are attempts at more precise definitions. The most famous one (and the most rigorous one I know of) is by Matthias Felleisen in his paper On the Expressive Power of Programming Languages (the first two pages contain a gentle introduction, the rest of the paper is more meaty).

The main intuition is this: when translating a program from language to another language, some of the changes you need to make are locally contained (such as e.g. turning FOR loops into WHILE loops or loops into conditional GOTOs), and some require a change to the global structure of the program.

When you can replace one feature of one language with a different feature of a different language by only local transformations, then these features are said to have no effect on the expressive power. This is called syntactic sugar.

On the other hand, if it requires a change of the global structure of the program, then the language you are translating to is said to be unable to express the feature. And the language you are translating from is said to be more expressive (with respect to this feature).

Note that this gives an objectively measurable definition of expressiveness. Note also that the notion is context-dependent on the feature, and it is comparative. So, if every program in language A can be translated to language B with only local changes, and there is at least one program in language B which can not be translated to A with only local changes, then language B is strictly more expressive than language A. However, the more likely scenario is that many programs in both languages can be translated back and forth, but there are some programs in both languages that cannot be translated to the other. This means that neither language is strictly more expressive than the other, they just have different features that allow different programs to be expressed in different ways.

This gives a formal definition of what it means to be "more expressive", but it still doesn't capture the psychological notions behind the phenomenon. For example, syntactic sugar, according to this model, does not increase the expressive power of a language, because it can be translated using only local changes. However, we know from experience that having FOR, WHILE, and IF available, even if they are just syntactic sugar for conditional GOTO makes expressing our intent easier.

The fact is, different languages have different features that make expressing different ways of thinking about a problem easier or harder. And some people might find one way of expressing their intent easier and others a different way.

An example I found in the Ruby tag on StackOverflow: many users who follow the Ruby tag claim that loops are easier to understand than recursion and recursion is only for advanced functional programmers and loops are more intuitive for newcomers, but I have seen multiple cases of complete newcomers who intuitively write code like this:

def rock_paper_scissors
  get_user_input
  determine_outcome
  print_winner
  rock_paper_scissors # start from the top
end

Which usually leads to several people commenting that "this doesn't work" and "they are doing it wrong" and the "correct way" is this:

def rock_paper_scissors
  loop do
    get_user_input
    determine_outcome
    print_winner
  end
end

So, clearly, there are some people for whom tail recursion is a more natural way to express the concept of "looping" than loop constructs.

Summary

The fact that two languages are Turing-equivalent says one and exactly one thing: that they can compute the same set of functions on natural numbers as a Turing Machine can. That's it.

It doesn't say anything about how fast they compute those functions. It doesn't say anything about the ease of expressing those functions. And it doesn't say anything about what else they can do besides computing functions on natural numbers (e.g. linking to C libraries, reading input from the user, write output to the screen).

does that mean that the class of problems that each programming language can solve acctually varies by language, even though these languages are all turing complete?

Yes.

1. There are problems that aren't covered by the term "Turing-complete" (which only concerns itself with computing functions on natural numbers) such as printing to the screen. Two languages can be Turing-complete but one can allow printing to the screen and the other not.
2. Even if both languages can solve the same problems, that doesn't say anything about how complex the encoding is, and how easy it is to express this encoding. E.g. C can solve every problem Haskell can, simply by writing a Haskell interpreter in C … but you have to write the Haskell interpreter first in order to solve a problem this way!

Answer 5

All Turing complete programming languages can implement the same set of algorithms. So, if you see that some algorithm is very difficult to be implemented in a particular language, it does not mean it is impossible.

Remember that a language consists of syntax and semantics. Sometimes, the set of words belonging to some language is not minimum to be considered Turing complete, there are features that make things easier (that’s why they are called features). If you take out those features, the language is still Turing complete.

Some of these might be of interest:

• Source-to-source compiler on Wikipedia

• On the importance of Turing completeness on Lambda the Ultimate

Answer 6

All Turing-complete languages can compute the same things.

If you try to implement a modern language, you'll notice that most of its features do not add any computational capabilities. Many of those features can be lowered to simpler ones that already exist in the same language.

Here are some examples:

• If you don't have enums, you can use integers.
• If you don't have buffers that know their size, you can create a type that contains a size and a buffer that doesn't know its size.
• If you don't have bounds checking of buffers, you can just check the index every time you use them.
• If you don't have variadic functions, you can create a function that takes a buffer that knows its size and read from that buffer the same information that you'd get from formal arguments.
• If you don't have operators, you can use functions.
• If you don't have types that can inherit each other, you can create types that contain each other and access them through an extra level of indirection, with subtyping being simply a transformation of the handle-to-the-entire-type to a handle-to-the-contained-type.
• If you don't have delegates but you have function pointers, you can create a type that contains the referent object and a function pointer.
• If you don't have delegates but you have interfaces, you can declare an interface that contains a single method with the signature you want.
• If you don't have generic types, you can use non-generic types that only assume the upper or lower bounds you are interested in (and maybe perform appropriate casts at the usage spots, to keep the compiler happy).
• If you don't have a linear/affine type system, you can just avoid using any variable more than once.
• ...and so on.

Mainstream language design focuses on features that make it easier and more convenient for us to compute things faster, recognize our mistakes earlier, program against unknown components, make parallelism safer, and so on.

The purely computational stuff were nailed down a long time ago.

Answer 7

The existing answers rightly point out that Turing completeness is not a good way to compare languages. Indeed, almost all languages are Turing complete. ("If everyone is special, then no one is special," as The Incredibles used to say.)

However, it is possible to compare the expressiveness of languages with mathematical precision. Take a look Felleisen's On the Expressive Power of Programming Languages. Roughly, the idea is to ask the following question: Can I convert any program in language A into a program in language B by making only local changes? In other words, Felleisen gives a mathematically precise form to your intuition.

Answer 8

On top of everyone else's answers, here's another analogy.

To wash clothes, you need three things: some reservoir which holds water, a detergent of some kind, and an agitation mechanism. This could be realised in many ways. The water reservoir is anything which holds enough water (e.g. a tub, a lake, a river). The agitation mechanism could be a mechanical device, a washboard, or even a rock against which the clothes are beaten. And detergents come in various forms, too.

So what's the difference between a modern computerised washing machine, and a rock next to a river?

It boils down to three things: efficiency, safety, and convenience. Some methods of washing use less energy, pollute the environment less, use less water, and so on. Some methods of washing require less repetitive manual activities (which result in injuries) or being outside in inclement weather. And some methods of washing don't require a human to babysit the process.

Turing-complete programming languages are general purpose, so they are put to more than one task. Nonetheless, for a given task, some programming languages are more efficient, more convenient, and safer (in the sense that less can go wrong when the program is actually used) than others.

Answer 9

Others have provided plenty of good answers, but they don't explicitly mention one caveat that once confused me a lot: Turing completeness doesn't imply that a language can express arbitrary computable functions from its inputs to its outputs. It is weaker: there must be some way of representing the domain and range of the set of computable functions as inputs and outputs such that each of these functions maps to a program that takes a representation of its inputs to the corresponding outputs.

Take, for instance, a language that expresses Turing machines. Each program in the language is a Turing machine.

Now consider the sublanguage of all Turing machines that read and write only the characters a, b, and blank. It is Turing complete, but it cannot express any programs that, for instance, produce c on all inputs, because it can't write any cs. It can only express all computable functions on inputs and outputs encoded as strings of as and bs.

So it isn't true that all Turing-complete languages can compute the same things, not even when we limit these things to be the computable functions from their potential inputs to their potential outputs. The language may require inputs and outputs to be encoded in certain ways.