Does it make sense to say if an OS is Turing complete

The book “Modern Operating systems”,
says

The Operating System is an Extended Machine.

So I wonder if an OS is a model of computaion, and whether it makes sense to say if an OS is Turing complete? Thanks.

Probably not.

Operating systems expose an API that provides services. Despite the apparent complexity, the vast majority of service calls in a OS API are just that: service calls, and nothing more. Operating systems do not typically provide looping services, or any of the other mechanics of a Turing-Complete machine; programming languages provide such mechanisms (i.e. the programming languages that call the OS API).

If an OS call does provide a looping service (e.g. traversing all the files in a folder) or some other operation that characterizes a Turing-complete mechanism, it does so at the behest of code written by some programmer in a Turing-complete programming language.

I would generally say “no” with a caveat.

The main difficulty is that the phrase “operating system” is very broad — an “OS” could be a standalone microkernel without any attached services, or an OS could be a multi-user graphical environment with a hundred subsystems, or anywhere in between.

When you decompose a modern operating system, you may find that it includes components or services which are Turing complete. For example, the “Debian” OS includes “bash” as a central part of the system — without bash (or some workalike), you wouldn’t recognize it as the same operating system. Bash, of course, provides a Turing complete programming language.

You might say that Debian is indirectly Turing-complete – because it has a Turing-complete component. But that’s misattribution. If you wanted to have a discussion about the computational soundness of Unix-style UX, you would talk to the authors of bash — not the authors of Debian.

This depends on how the operating system is implemented, and on how you answer the question of what is part of the operating system and what isn’t.

As other answers have already commented, an operating system may provide a scripting language as part of its shell. Whether this can be said to make the system itself turing complete is a question of semantics: is the shell viewed as being the operating system. Many would answer “no” – a shell is just user interface, the operating system itself is lower level than that.

In most cases, an operating system is implemented as an abstraction layer on top of hardware. The hardware provides processing, and both user software and the OS are implemented using it. In this case, it’s quite clear that the operating system itself is not turing complete – the underlying hardware provides that property.

But there a handful of cases that are different, primarily in academic research systems:

In some systems the hardware and operating system are inextricably linked in such a fashion that from an end-user perspective it does not really make sense to distinguish one from the other. An example would be CAP or the Flex machine.
In some systems the operating system provides a programming language that all user applications must be written in, or a virtual machine that they must use. Examples include the LISP Machine OS aka Genera and Microsoft’s Singularity.

In either of these cases, the answer is probably yes.

Operating Systems Are Languages. And Operating Systems Are Machines. So, yes, it does in fact make sense to talk about all the same things that we talk about for Languages and Machines: Computational Power, Expressivity, Orthogonality, Compositionality, Modularity, etc.

The fact that Operating Systems Are Languages seems to be so obvious that there isn’t even any discussion about it that one could link to. The dual (Languages Are Operating Systems) seems to be discussed more vividly, and there is a quote on that page saying:

The converse, that operating systems are languages is widely known. Where does an OS designer get inspiration from if not from various languages? This is especially true in the case of functional languages. (Damn those bastards, always twenty years ahead of the rest of us.)

(Emphasis mine.)

A Turing machine is one of a particular set of mathematical constructs that take a string as input and either return “true”, return “false”, or never return.

To say a Turing machine U is a universal Turing machine is to say there is a way to take any Turing machine M and any input string I and represent (M, I) as exactly one string S such that if M returns a result for I, then U returns the same result for S.

To say a programming language is Turing complete is to say the interpreter is a universal Turing machine. (The combination of a compiler and the computer on which the compiled code runs could be called an “interpreter”.) The program is the input string to the interpreter, and the output value is whatever we choose to observe about the interpreter’s output when the program is run — a certain character printed to the console could mean “true”, a zero status code could mean “true”, etc.

The difficulty of saying whether an OS is Turing complete lies in the difficulty of defining what its input and output are. It is trivially Turing complete if you define its input as the combination of its file system (where an executable file can be stored) and its shell (where a command can be entered to run an executable file). If you can use the shell directly to write to a file (e.g. echo "this is my program" > program.txt), run a compiler on that file, and then run the compiler’s output, then the shell itself is trivially a Turing machine. In some OSes, the shell is nontrivially a universal Turing machine, even without touching the file system, thanks to a shell scripting language.

For any given general purpose operating system, there are probably many more creative ways to define its “input” and “output” such that it is a universal Turing machine. This could actually be a bad thing, because that would mean there is a creative way to cause the OS to go into an infinite loop and become nonresponsive.

Filed under: softwareengineering - @ 19:58

Thẻ: operating-systems, turing-completeness

Thiết kế website giá rẻ

Danh mục

Does it make sense to say if an OS is Turing complete