“Malware” is just short for “malicious software”. Software is malicious if it was written with malicious intent, which is intent to cause harm. (Technically it doesn’t even need to succeed at causing harm, or even have the capability of doing so, it just needs to have the intent of causing harm.)

Therefore, by definition, if the machine that you are using is capable of running software (using whatever definition of software you care to use, and regardless of whether or not it is Turing Complete) it can run malware.

Malware’s goal is to find a security vulnerability so that it can give itself permissions to perform actions on the attacked computer that the computer’s security would not otherwise allow, up to and including deletion of files, wiping the hard disk, copying itself to other computers, and other types of mayhem.

To illustrate, I’ll cite two examples:

1. SQL Injection
2. Buffer Overruns

SQL injection is prevented by using prepared statements. Buffer overruns are prevented by doing bounds checking on arrays. ANSI SQL is not Turing complete. The C language (which is where most buffer overruns occur in the wild) is Turing complete.

The way you build a programming language that is resistant to hacking is by sandboxing it in certain ways. Many modern languages, for example, simply do not allow you to access elements beyond the end of an array, so they are not vulnerable to buffer overrun exploits.

No. It is not possible in the general case to define and discern the purpose of Turing complete code. This is somewhat related to the halting problem and is something that DRM must grapple with constantly (go ahead and try to distinguish between malware and DRM – one is protected by law in the US and the other is against the law in many places, interestingly enough).

The way we have generally solved the malware problem is by requiring the user to grant necessary permissions to programs. This prevents programs from accessing resources outside of the permissions. This, of course, will fail in as many cases as you’d expect based on the user, but it moves the onus to the user from the system.

I think this is a good question, but it doesn’t really have the simple answer others have tried.

The most basic problem that malware exploits is the required, and even desired, sharing of resources between the simulated Turing machines of computer programs. The fundamental limitation of a computer that prevents it being a perfect Turing simulant is finite resources; conceptually, the symbol tape of a Turing machine is of infinite length, meaning the machine has access to infinite state data which it can read or write as it chooses. The inference is also that each Turing machine gets a separate tape on which to work, and the state data of any single Turing machine is never seen by another machine, unless that data is provided as the initial state of the second machine’s tape. Neither of these are possible, and sometimes not even desirable, in a real computer; we like our computers to multitask (to simulate multiple Turing machines simultaneously), meaning that we must efficiently divide and re-use our finite resources, and in general we actually like it when one program knows what the heck is going on in another program.

A second and related problem is that the conceptual Turing machine doesn’t have to worry about the long-term persistence of its data; it “writes” state symbols to its tape and expects that state to persist indefinitely, whether the machine ever returns to that position of the tape or not. In a computer, there are practical concerns about fast but volatile memory versus slower must more persistent memory. This generally necessitates a transfer of memory between volatile and persistent forms that our program, a Turing simulant, ideally shouldn’t have to care about.

A third problem is that Turing machines are automatons (Turing’s original term was “automatic machine”). They do exactly what they’re told to exactly what they’re given, nothing more or less. A more intelligent actor is required to configure (program) the machine to do the right thing and give it the proper initial data. That actor must have good intentions, and their resulting design must function correctly in all circumstances.

It is possible, in theory, to create an operating system that can maintain multiple Turing machines without allowing the sharing of resources. However, to do so, the following conceptual rules must be followed:

• No sharing of volatile memory between multiple Turing machines executing concurrently.
• No sharing of persistent memory between multiple Turing machines, whether executing or not.
• Any deviation from the first two rules must be performed directly by the intelligent owner of the computer, who must be assumed to be benevolent and infallible.

It’s that last rule that is problematic to our modern use of computing devices and very likely puts the kibosh on the whole thing. The absolute prohibition on shared resources between machines (programs) means that the programs being executed by a computer can only ever be provided with initial state data, and can never be given new data while running by external sources (at least not without stopping the program cold and resetting its tape with new data before restarting it).

The requirements that the intelligent actor actually be benevolent and infallible are beyond the scope of a computer (though we try), and the directive that the actor must directly make any state changes requires the actor to have the knowledge and skill to do so, as well as the ability, good intentions and perfection of operations. Modern operating systems, especially in consumer devices, typically assume the opposite of all of this; that the user does not possess the knowledge, skill, good intention or perfection to make necessary data changes directly, and so does not give them the ability. This is usually a good assumption to make; I program for a living, and yet would have no clue how to make direct changes to the binary data of a program currently running on my Android phone.

However, if the actor can’t change the data of a program directly, then the system will either only run the machines it was initially given with the data they were initially given forever (possibly good for complex, open-ended mathematical computation, such as figuring out pi to the bajillionth place, but not real good for updating your Facebook profile when you can’t even load that profile into the memory of a running program), or the operating system must provide a means for the actor to make some changes that are desirable in a safe way. This is typically by providing the user with one or more other machines, that violate the “no shared resources” rule in order to change the data in a way that is assumed to result in correct and desired changes in execution of the program that really owns that data.

This is where malware gets in. Simply being required to allow violations of the no-shared-state rule, for any reason, allows multiple machines to make changes to data that they all depend on. The assumption that must be made is that all designers of all these programs are benevolent and infallible. Neither are true of human computer programmers, who are the ultimate endpoint in the design of any program, no matter how many steps along the path of generating the machine code for the program are automated. A fallible programmer can introduce an error in the program that causes it to corrupt not only its running state but cause problems with any other program using the same data. A malevolent programmer can intentionally do similar things.

So, until machines start doing all our coding for us, while it may be theoretically possible, it is practically impossible to create a system that is usable by and useful to the average end user of a computer product in our modern society, that has zero chance of being affected maliciously.

The original answer I gave was, I think, correct and useful, and I didn’t want to blow it away, but I think the answer can be arrived at much more concisely.

There are some assumptions that are typically made about Turing machines, which are the basis for calling any other machine including a logical one “Turing complete”.

• One tape per machine and one machine per tape. In other words, “no shared state”.
• Only the machine alters the tape’s data from the initial state given to it when it starts; “no dynamic input”.

Therefore, theoretically, you could design a system that, with some understood limitations (like finite resources), would simulate a single-tape Turing machine, and such a system would be impervious to malicious software (or even bugs caused by human fallibility), for the simple reason that none of the Turing machines the system may simulate at any given time, or indeed has ever simulated, could ever affect the execution of another machine.

But real computers don’t work that way; or at least, we don’t want them to. We like programs, and even full systems, to share information. We like programs to ask us for input halfway through, and to accept input that may fundamentally change the way the program executes. Sometimes, we even like one program to change the state of another program on our behalf. Our programs therefore allow us to do these things for benevolent purposes; performance, memory economy, automation, ease of use.

However, this same willingness to share resources requires the assumption that all actors or agents of actors that are sharing the resource are doing so benevolently and infallibly. Neither is an adjective that applies to 100% of computer programmers or the programs they write to act on their behalf. This is how malware gets in; we allow what is technically a violation of the behavior of an ideal Turing machine, in order to perform a task that allows a desirable change in the behavior of a program. That same accepted violation allows someone to do the same thing to effect an undesirable change in behavior.

Malware, you know malicious software, can be broadly defined as software that performs a function you don’t want it to perform. Beyond a simple bug or error, the goal of the software is counter-productive to the user’s welfare. Like providing access to those that shouldn’t have it, wiping data, or say, tracking your actions and reporting them to a third party.

So while it’s somewhat awkwardly asked, I’m going to go with yes, executing software that is given enough freedom to qualify as “Turing Complete*” has enough freedom to at least attempt to be malicious. Operating systems by and far are made to run other programs within them and so they should be made with the knowledge that the software could be malicious. Hence, access privileges, passwords, and memory management.

*Being Turning Complete involves an infinite amount of memory by the way. It’s a term that gets thrown around a lot into situations where it really isn’t warranted. I think you mean “software written by other people”.