1
$\begingroup$

To what extent is the abstract model of computation specified by the x86 language Turing complete?

The above question is related to this question:
Is C actually Turing-complete?

In theoretical computer science the random-access stored-program (RASP) machine model is an abstract machine used for the purposes of algorithm development and algorithm complexity theory.

The RASP is a random-access machine (RAM) model that, unlike the RAM, has its program in its "registers" together with its input. The registers are unbounded (infinite in capacity); whether the number of registers is finite is model-specific. Thus the RASP is to the RAM as the Universal Turing machine is to the Turing machine. The RASP is an example of the von Neumann architecture whereas the RAM is an example of the Harvard architecture. https://en.wikipedia.org/wiki/Random-access_stored-program_machine

Improve this question
$\endgroup$
11
  • $\begingroup$ C can do I/O with devices with unbounded storage capacity, e.g. tape drives, but granted, that really isn't a language feature. $\endgroup$
    – reinierpost
    Mar 13, 2020 at 23:17
  • $\begingroup$ @reinierpost Is this literally unbounded? $\endgroup$
    – polcott
    Mar 13, 2020 at 23:36
  • 1
    $\begingroup$ @reinierpost Unbounded is not exactly the same thing as infinite. Always as long as needed for a particular computation may never actually require infinity, unless one is counting to infinity and storing the result of each step. $\endgroup$
    – polcott
    Mar 14, 2020 at 2:34
  • 1
    $\begingroup$ As I mentioned prevoiusly, please define what you mean by a "computation". Is it a computational problem? Is it a run of a particular Turing machine on a particular input? Something else? If a computation is a a run of a particular Turing machine on a particular input (which is my best guess for the standard meaning), then I can't understand what what meaning you would assign to a computation "that can be completed on an x86 machine". $\endgroup$
    – D.W. ♦
    Mar 15, 2020 at 23:36
  • 1
    $\begingroup$ I guess you cannot look at the outside world as an unlimited tape for the x86? If you include I/O then your x86 can read and write to the outside world within the limits of the finite size of the universe. But something outside the x86 would have to cooperate. $\endgroup$
    – Bobby Durrett
    Aug 15, 2020 at 0:04

4 Answers 4

Reset to default
6
$\begingroup$

The difference is: since x86 machines are finite, Turing machines can decide languages (decision problems) that cannot be decided by any x86 machine.

As I explained before, the idea of 'the set of decidable computations' is a category error. Decidability is a property of formal languages (or equivalently, of decision problems), not of computations. So, no, the statement in the second paragraph of your question is not correct. It's not even wrong -- it is neither true nor false.

I suspect that perhaps you have found a statement of the Church-Turing thesis that is worded in a way that is confusing. I suggest reading a standard reference on the Church-Turing thesis, and don't rely solely on the wording you have bolded.

It is true that every decision problem that can be solved by an x86 machine can be solved by a Turing machine (or, equivalently, every language that can be decided by an x86 machine can be decided by a Turing machine). This is true because you can program a Turing machine to simulate the behavior of an x86 machine. However, the converse is not the case: any real x86 machine has a fixed and finite amount of memory, while a Turing machine can use an unlimited amount of storage on its tape, so there are decision problems that can be solved by a Turing machine, but not by an x86 machine. (Even if we take into account the amount of storage provided by disks, disks use fixed-length addresses, so there is a fixed and finite upper bound on the maximum amount of disk storage that can be addressed from a standard x86 machine.)

If you wanted an x86 machine to be equivalent in power to a Turing machine, you'd have to provide some way to extend its amount of storage without limits. If you had a way to do that, then yes, any decision problem that can be decided by one could be decided by the other: each one could simulate the other.

Improve this answer
$\endgroup$
8
  • $\begingroup$ "the idea of 'the set of decidable computations' is a category error." (1) There is a set of computations that a Turing Machine can perform and (2) There is a set of computations that machines having limited memory can perform, and (3) There is a difference between these two sets. That there is a lack of existing terminology to name this set does in no way show that this set does not exist. $\endgroup$
    – polcott
    Mar 14, 2020 at 4:58
  • 3
    $\begingroup$ @polcott, the phrase 'decidable' is standard terminology with an accepted definition. Using it in a way that is contrary to that is confusing. You asked whether the statement is correct, and I'm telling you that statement is not correct; I'm also sharing some statements that are correct. $\endgroup$
    – D.W. ♦
    Mar 14, 2020 at 15:38
  • $\begingroup$ If you pay very close attention you may find that you never got around to directly answering the actual question. Exactly what computations can be completed on a Turing Machine that cannot be computed on an x86 machine? en.wikipedia.org/wiki/Random-access_machine A machine could be defined that forms a linked like of pointers relative to the current location thus enabling unlimited memory to be addressed. $\endgroup$
    – polcott
    Mar 14, 2020 at 18:16
  • 1
    $\begingroup$ @polcott, the only question I see is "Is this correct?" and I think I answered that. The question in your comment might be a different question and might be best asked separately. If you do that, I hope you'll define precisely what you mean by a "computation". (Is it a computational problem? Is it a run of a particular Turing machine on a particular input? Something else?) Of course you could define a third type of machine that is neither a Turing machine nor a x86 machine; if that's what you want to ask about, I hope you'll say so. $\endgroup$
    – D.W. ♦
    Mar 15, 2020 at 17:48
  • 2
    $\begingroup$ @polcott, oh, actually, no, I didn't see that. Sorry. Please don't put the primary question in the title. The title should be a summary of the post, and the body of the question should stand on its own. I encourage you to make sure the question you want answered is in the body of the post. $\endgroup$
    – D.W. ♦
    Mar 15, 2020 at 19:41
3
$\begingroup$

For a real computer, everything is decidable. There is a (far bigger than astronomically but) finite number of possible states, so any program will eventually halt or enter the exact same state a second time, in which case it will never halt.

Of course that is purely theoretical. It is (based on quantum physics and the total energy in the universe) physically impossible to run a 256 bit counter from zero to $2^{256}-1$.

(Deleted my comments responding to someone who is unwilling to understand).

Improve this answer
$\endgroup$
3
  • $\begingroup$ That is only 87 ASCII decimal digits or 348 {"0", "1"} binary digits, thus a program that counts from zero to 2^256 could be written in a few kilobytes. $\endgroup$
    – polcott
    Mar 14, 2020 at 18:36
  • $\begingroup$ It certainly is not physically impossible to make a tiny little "C" program that counts to: 2^256= 115792089237316195423570985008687907853269984665640564039457584007913129639936 using ASCII digits. The universe would die of heat death long before it gets done, but the program could still be written and executed in a very tiny amount of space using very conventional technology. $\endgroup$
    – polcott
    Mar 16, 2020 at 16:57
  • $\begingroup$ The point is that it is apparently not impossible for the reason that you claimed. $\endgroup$
    – polcott
    Mar 17, 2020 at 19:55
0
$\begingroup$

RIP relative addressing of the x86 language provides access to unlimited memory

An abstract machine having a tape head that can be advanced in 0 to 0x7FFFFFFF increments an unlimited number of times specifies a model of computation that has access to unlimited memory. The technical name for memory addressing based on displacement from the current memory address is relative addressing.

I am focusing on building a precise bridge between conventional high level concrete programming models (none of which can possibly be Turing Complete) and the closest abstract model that is Turing complete. To do this we must necessarily make at least minimal adaptations to the concrete model.

One concrete model of computation requiring very little change to adapt it to become a Turing complete abstract model of computation is the 32-bit signed RIP relative addressing of the x86-64.

If we take this machine language and get rid of all absolute addressing modes, leave the size of memory and the width of the instruction pointer unspecified then with these minimal changes the abstract model based on the x86-64 becomes Turing complete.

Improve this answer
$\endgroup$
10
  • 4
    $\begingroup$ I am sympathetic to this answer. I like it. But, I think it highlights a possible ambiguity in what you mean by "the x86 architecture". It's my understanding that the original x86 architecture specified 40-bit physical addresses (so it wasn't possible to have more than $2^{40}$ bytes of memory), and the current x86-64 architecture specifies that physical memory addresses are 48 bits (so it's not possible to have more than $2^{48}$ bytes of memory). Consequently, despite the existence of relative addressing, memory is finite and limited, and such a model is not Turing-complete. (continued) $\endgroup$
    – D.W. ♦
    Aug 14, 2020 at 18:47
  • 1
    $\begingroup$ If we consider that restriction to be part of what we mean by the x86 architecture, then this answer is not correct, and the x86 architecture is not Turing-complete. Alternatively, if we envision some architecture that supports these relative-addressing instructions but with no limits on addresses, the answer might be different -- but it's not clear to me exactly what the specification of that architecture would be, since I think the assumption of fixed-size addresses is baked into the x86 spec in many ways. $\endgroup$
    – D.W. ♦
    Aug 14, 2020 at 18:47
  • $\begingroup$ @D.W. See the edits. The x86 language specifies an abstract model of computation that is Turing Complete. $\endgroup$
    – polcott
    Aug 14, 2020 at 19:27
  • $\begingroup$ @D.W. I changed my original question to correspond to the answer that I found: To what extent is the abstract model of computation specified by the x86 language Turing complete? $\endgroup$
    – polcott
    Aug 15, 2020 at 5:37
  • 1
    $\begingroup$ I like it. I think it's a great insight, about how relative addressing for control transfers suffices to obtain access to memory of unlimited size. Good stuff! $\endgroup$
    – D.W. ♦
    Aug 15, 2020 at 5:38
0
$\begingroup$

Mapping x86 programs to a Turing equivalent abstract model

The following abstract machine maps the x86 language to machines with a fixed pointer size of the largest unlimited integer address that is actually needed by the computation.

Instruction
     : INTEGER ":" OpCode
     | INTEGER ":" OpCode Integer
     | INTEGER ":" OpCode Integer "," Integer

HEXDIGIT [a-fA-F0-9]
INTEGER  {HEXDIGIT}+ 
OPCODE   HEXDIGIT{4} 

Address:OpCode
Address:OpCode Param
Address:OpCode Param, Param

Computational equivalence means that two machines will always produce equivalent output for equivalent input or fail to halt on equivalent input for a set of computations.

The set of computations not requiring more memory than is available for x86/x64/C computations will always have corresponding output for corresponding input or fail to halt on corresponding input exactly corresponding to the behavior of a Turing machine on equivalent input.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This answer is not comprehensible. I have refrained from voting as it would be serial voting. $\endgroup$
    – user253751
    Sep 20, 2021 at 8:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.