Can a language be turing complete but incomplete in other ways?

Question

For example, are there certain things when writing an operating system that cannot be accomplished in a turing complete language?

Answer 1

Depending on context, "accomplishing something in a language" means different things to different people. Turing is one of those people, and he defined very precisely what he means by "complete".

If a language (or a theoretical machine) is Turing complete, there are no Turing computations it cannot do. This does not imply that the language is omnipotent, just that it is good at sums. There are many "things" which are not Turing computations, and which therefore a Turing-complete computer may not be able to do.

"Be an operating system" is not a Turing computation. To be an operating system, you need to do more things than just computations. You also need to manipulate hardware.

Given a Turing complete language, together with a set of operations for doing all the hardware manipulation that you need, including a suitable concept of input and of time, you can write an OS. Or I should say, it is possible to write an OS. Whether you personally can do it depends on how easy the language is to work with, and on physical limitations which the Turing definition ignores, such as whether the resulting program would actually fit and execute in the memory of the device you want it to operate, and run in a realistic time.

Ignoring practical limitations though - yes, you can write an OS in any Turing complete language, provided that the language also has sufficient operations to drive the hardware. "Library calls", if you wish to take the practical CS approach of distinguishing language from libraries. Turing made no such distinction, because his computing model doesn't have the concept of a "call" anyway. You also need to solve the bootstrap problem - either your hardware must directly run the language you're writing in, or else you need a compiler into a language which the hardware does run, or else you need an interpreter written in a language which the hardware runs. Again, Turing ignores all this because his computation model uses abstract hardware, whereas writing an OS is all about the hardware.

In English (rather than CompSciSpeak) it is common to say that a language "lacks certain features", and arguably that it is therefore "not complete" by comparison with another language which has them. One might counter-argue that it is possible to implement closures in C. One can for example write a C program which is a Lisp interpreter, and embed in it a Lisp program as a string. Voila, closures in C. However, this is not what most people are asking for if they say, "I wish C had closures". If you think every language needs closures, then C is incomplete. If you think every language needs structured programming, then ARM assembler is incomplete. If you think it should be possible to dynamically add methods to an object, then C++ is incomplete, even though it's perfectly possible to write a C++ class with "AddMethod" and "CallMethodByName" methods and fake up your own method calling convention from there. And so on.

Turing doesn't think languages need any of these conveniences: they don't affect what computations can be performed, just how easy it is to write certain programs. The concept of Turing completeness has nothing to say about what programs look like, or how they're organised, only what they output. So those languages are Turing complete, but from the programmer's point of view there are certain things which cannot be accomplished in those languages.

Answer 2

No. or at least if you found one that would be a disproof of the Church Turing Thesis.

However, there are languages that are Turing complete but in which it is a complete pain in the ass to write certain programs, i.e., string processing in FORTRAN, numerical programming in COBOL, integer arithmetic in sed, practically everything in x86 assembler.

And then of course there's brainfuck.