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?

Endorsement

Answer 1

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.

Mesomorph

For some reason the link to Church-Turing isn't surviving formatting. en.wikipedia.org/wiki/Church–Turing_thesis – Mesomorph

Fixed the link for you. For some reason, certain browsers don't properly escape URLs when you copy them... – Colonize

Groovy, thanks. The text in the link looks right when I save it, so that was non-obvious. – Mesomorph

Yeah, that happens a fair bit - the client-side Markdown preview engine is much more forgiving than the server-side rendering engine. – Colonize

-1 -- there are formal languages that are not recursively enumerable. – Eada

So, Dave, I take it you're suggesting that there are things that are "reasonable computations" that can't be computed by a TM? Would you care to exhibit one? – Mesomorph

I will donate one shiny dollar to the first person to write a functioning bootloader in brainfuck – Cobber

NOTE: Despite that it was accepted, this answer is wrong. When writing an operating system, you need to be able to do things other than read input, do universal computation, and write output. You'll need to be able to interact directly with the hardware in order to manage a filesystem, say, or print a document to a printer. These are all things that an OS needs to be able to do that many Turing Complete languages just don't have provisions for. – Recognizance

@Recognizance don't make mathematical statements you don't understand. What you've just done is restate my second paragraph. Proof: you can certainly do those things in machine code. Any Turing-complete language can then be used to write an assembler to generate the needed machine code, or to insert that code in memory. Thus with enough effort any Turing-complete language can indeed interact directly with the hardware, which suffices to disprove your assertion. – Mesomorph

Answer 2

Yes, you can have a language that does not allow you to manipulate the hardware directly. It would be hard to write an operating system using the Bourne shell, for example. But these limitations are less than you think. Operating systems have been written in Standard ML, Scheme, and even Haskell!

Londalondon

Hmm... turing machine is turing complete, right? and how does it allow to "manipulate the hardware directly"? – Dilatation

I mean "manipulating the hardware directly" is not a question of language completeness. Language is incomplete if, for example, it does not have goto, loop operators and subroutines, so you are unable to write cyclic program. – Dilatation

In bash you can write cat, ls, grep, ping, etc. So why can't you have commands for reading/writing data from/to hardware port. It will still be bash. – Dilatation

@Pavel: The question was, "are there other interesting notions of completeness". My answer was, "yes, access to the MMU page tables and other hardware." cat, ls, grep, ping are written in C not bash. If you only have bash, and you have no Unix system calls, I don't think you can implement Unix system calls. – Londalondon

Interesting idea. Although I'm not sure if access to hardware should be counted as a property of a language. Most languages I know have hardware/os access implemented as external libraries written in another language (mostly c/c++) and can be run without those libraries. Look at most dynamic languages, java/.net etc. – Cocker

My answer was "access to the MMU page tables and other hardware" is not a primary language concern and is not related to language completeness. It is incompleteness of something else. Of course to keep it simple you may say it is incompletenes of language, and you would be understood, but this kind of incompleteness is far different from the one Turing was thinking about. You write "mov ax,bx" and it's up to CPU to perform this operation. You write "cat /etc/passwd" and it's up to OS to perform this. It's environment/compiler concern. You write for(int i=0;i<10;i++){} - then it is language. – Dilatation

bash without system calls is useless. If you have system calls - you may have anything because bash is Turing-complete. If bash was not T-complete, for example did not allow to make loops, you can not do certain cyclic things even with system calls. Language needs a way to interact with environment, otherwise it is not T-complete - without any interactions you can not compute every Turing-computable function because you can not read parameters. Just don't mess incompleteness of ecosystem(lang,tools,compiler,environment,etc) with language incompleteness. – Dilatation

@Pavel: Right. Check the question. The question is about "incompleteness of something else." The horse is dead; you can stop beating it... – Londalondon

Turing-completeness is pure language property. You can analyze language isolated and decide if it is T-complete or not. This sort of completeness if very different from the one you are talking about - hardware access, etc. Sure, you can say "bash does not have hardware access and c++ does" and you would be understood. And that's true in a context of modern IT industry. However, if you imagine runnig c++ program on computer that does not have cpu with registers, but have something else, then - c++ language still is T-complete, but there is not hardware access support. – Dilatation

If I read t right, question is about incompleteness of language and inability to accomplish things in T-complete language. And the answer is - in T-complete language you can do anything, you just need compiler. If there is no compiler - it's not a language incompleteness. And language is incomplete in other sense if it does not help doing OOP, functional programming and other useful things that don't affect T-completeness. – Dilatation

Answer 3

Turing-complete is most general formal definition of completeness. There are language features that are necessary for certain applications, but these don't fit into the formal definitions.

For example, graphics capabilities, ability to spawn background processes, ability to persist state, and ability to connect to the network are all useful features, but don't relate to a language's Turing-completeness. So Python on Google App Engine or a Java applet running in a sandbox is still Turing-complete.

You'll notice that in many cases, these types of features are provided by libraries, rather than the core language.

Warbeck

"graphics capabilities, ability to spawn background processes, ability to persist state, and ability to connect to the network are all useful features" - in most cases they are not language features at all, they are in libraries. Ability to make your class field protected or private, add attributes to method, etc - these are features that are useful, but not necessary for completeness. – Dilatation

Oh, guys, how do you think the libraries are written? – Mesomorph

Answer 4

If you're speaking of pragmatics, then certainly... you can imagine a programming language with no ability to read or write files (e.g. a language that can compute any function on integers but that's it)... Just because a language can't operate my toaster doesn't mean it's not Turing-complete, but it does mean there are things it cannot do, so I am not sure how 'important' or useful this distinction is.

Pash

"You can imagine a programming language with no ability to read or write files". Yes, c++ for example. fopen, fread, fclose are not part of language, they are in library. x86 assembler for example - no files at all. just hardware interruptions. – Dilatation

Any turing-complete language can operate your toaster, you just need compiler. – Dilatation

"Just because a language can't operate my toaster doesn't mean it's not Turing-complete, but it does mean there are things it cannot do" - if language is Turing-complete, there are no things it can not do. There are things you need better compiler and environment to do. Language can or can not do loops, classes, functions, attributes, templates, data structures. Compiler can or can not translate this language to CPU (or other environment, like JVM) instructions. – Dilatation

@Pavel: You need the toaster to be (software-)programmable in first place. Only in that case you can say that "you just need a compiler". – Bop

"If language is Turing-complete, there are no things it can not do." That's not quite it. If a language is Turing-complete, there are no decidable problems it cannot solve. It cannot necessarily interact with the toaster, but it can emulate a toaster, mathematically speaking. It also cannot decide the halting problem, as no Turing machine can. – Sweaty

Answer 5

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.

Behindhand

Answer 6

Language can or can not do things like - subroutines, recursion, custom data types, loops, defining classes, goto, etc. Set of such language features makes it complete or not. For example language is incomplete if you don't have loops, gotos and subroutines - you can not perform any cyclic operation. Language completeness is very theoretic and scientific thing. Like, for example, it's proven than even if your language does not allow to call functions recursively, but allows function pointers - you can simulate recursion, i.e. with y-combinator.

Stuff like working with files and hardware very often is not a part of language. To accomplish any programming task you need more than language. You need environment your program works in. In x86 as language you have instruction "int" with single parameter, but it is up to OS to perform certain operations when you execute "int 21h".

Language just needs some way to communicate with environment and be complete - then it's up to environment to work with it. It's valid to write in x86 asm "mov ax,bx" but it is up to your CPU to perform this operation.

Being incomplete in some other way - easy, just define your own version of completeness. i.e. I hate to work without class-based OOP, so let's define that language is not Feldman-complete if it does not have language features supporting class-based OOP. Ok then, C and Javascript is not F-complete. You still can do anything in those languages, and even simulate class-based OOP to some level.

Regarding OS - you still need processor that runs instructions and compiler that translates language into CPU instructions. I can imagine compiler translating anything to machines codes. Like, following is valid JS code

for(var i=0;i<10;i++){
 mov("ax",i);
 int(0x21);
}

and it should not be that hard to compile it into machine code.

In modern world you choose not only language, you also choose platform, standard and non-standard libraries, literature, community, support, etc. All those things affect your ability to do certain thing, and they taken altogether may be or may be not "complete enough" for your task. But if I can not compile c++ code to java applet, it does not mean it is a c++ language incompleteness. It's just absence of compiler that will transform c++ code to something that can be loaded by JVM.

If you want, you can design a language with language features like "OpenFile, PingNetworkHost, DownloadMpeg4FileOverHttpsAndPlayBackwards". But if the language does not have them, they can still be implemented with other language features and environment support, so absence of such features does not make language incomplete. If your language is like C but without goto operator, loop operator (for,while,do while) and functions, then you can not write cyclic program and no environment and libraries can help you.

Dilatation

Answer 7

The answer is a most definite yes. Turing completeness only implies that a Turing complete language can be used to compute any computable function. For one, it doesn't say anything about the complexity of a computation.

You can usually expect that any polynomial time algorithm can be expressed as a polynomial time algorithm in any other Turing complete language, but that's about it. Especially any real time requirements (soft or hard) go out of the window, if your only focus is Turing completeness.

Another important thing is expressiveness of a language, which is largely a subjective property, but you can appreciate that programs are much harder to write in any machine code than, say, Java.

As for operating systems, an interface to the hardware is a must, but any language can be fitted with such utilities.

[Edit] Another thing I might add is that no actual implementation of any programming language is Turing complete by the nature of our finite computing machines. While the Church-Turing thesis, along with related seminal discoveries (like the halting problem), lay a foundation to our understanding of computing, they rarely meet the world of practical computing.

Unspeakable

Answer 8

Incomplete usability :)

Kutzer

Answer 9

When the talk is about languages, it is usually assumed that the languages run on some very simple machines. As such any concept of reading from a file or accessing the network is not normally considered in regards to the power of a language.

There is different classes of languages that are often used in computability theory (each with nearly endless modifications)

1. Finite automaton. This is the simplest class of machines and they can recognize the smallest class of languages, which happens to be the exact languages that regular expressions can recognize, ie. whether a string begins with two 'a's and end with d. They cannot be used to recognize whether a string contains a balanced set of parentheses, fx.
2. Push down automaton. This is essentially an extension of Finite Automatons with a stack. Unlike finite state machines, they can be used to tell whether a particular string contains a balanced set of parentheses. The languages that push down automatons can recognize is exactly the the set than can be described using context free grammars and they are often used to parse source code.
3. Turing Machines. These are the most powerful of the class of machines here, but that doesn't mean that they can be used to answer all questions. They are incapable of answering the question does this string describe a Turing machine that will run for ever? In fact any a Turing machine cannot tell anything about the non-trivial properties of any Turing machine (Rice Theorem).

So yes a Turing machine has limitations, and there are classes of machines that can do something a Turing machine cannot, but they have (all will in all probability) only ever existed in theory, newer in practice.

Work

Answer 10

I don't think definitions of completeness other than Turing (or regular expressions, or push-down automata) are relevant for languages. But this completeness is only with respect to the numeric or symbolic computing facilities.

The things you are mentioning seem to me to be more a function of the runtime and environment than the language. There's an important distinction, and formal notions of completeness typically only apply to languages themselves.

Deep