0
\$\begingroup\$

Given a certain instruction set, and that any high-level code is just converted to machine code anyway, then except simulating human intelligence, is it sufficient enough to do anything you want a computer to do?

For example, can the instruction set of the Arduino be used to generate high definition graphics on a modern computer monitor and play games? Why or why not?

*Note: I mean the Arduino instruction set only, not the board itself.

| improve this question | |
\$\endgroup\$
  • \$\begingroup\$ Yes. You may find there's time for a cup of coffee between screen updates, (and assuming you've added page switching to let it address enough memory) but in principle an Atmel AVR could do it. \$\endgroup\$ – Brian Drummond Apr 21 at 12:02
  • \$\begingroup\$ Why do you assume that a given instruction set can not simulate human intelligence? I don't know of any justification for that statement, based on the lack of other constraints you have given. \$\endgroup\$ – Elliot Alderson Apr 21 at 16:24
7
\$\begingroup\$

Once a programming language is 'Turing Complete', it can be used to emulate any other language. The only difference is then speed.

The instruction set of all MCUs is Turing Complete. It couldn't really be otherwise, they would not work as MCUs if they were not.

The provision of more instructions above the minimum needed for Turing Completeness makes the compiler easier, and the program faster. For instance you could do everything with a load/store to a single accumulator. However, being able to do arithmetic between several registers allows faster code.

According to this wikipedia page, a properly chosen single instruction can give you a Turing Complete machine. However, trying to program such a machine is really an exercise in what's theoretically possible, rather than having a useful MCU.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ What What? Hey Hey! What What? ... \$\endgroup\$ – Russell McMahon♦ Apr 21 at 12:11
1
\$\begingroup\$

Arduino is not an instruction set. Arduino programs are C++ code and libraries, compiled to machine code of the whatever CPU/MCU it is targeted to, for example AVR, as the Arduino platform runs on many architectures.

Yes, any CPU/MCU can compute anything you want since all it executes are the instructions. The limitation is how much time the computations take and whether there is enough memory to store instructions and data.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ "Arduino is not an instruction set." - I know. \$\endgroup\$ – Noob_Guy Apr 23 at 14:28
  • \$\begingroup\$ @Noob_Guy OK. But you did specifically ask about Arduino instruction set. Twice. If you did not mean to refer to Arduino instruction set but something else, I can't know what you meant. you can hit the edit button to update it. \$\endgroup\$ – Justme Apr 23 at 14:49
-1
\$\begingroup\$

The Turing-Church Thesis suggests the computational equivalence of

(1) Turing Machine

(2) certain recursive grammars (akin to human sentences)

(3) primitive-recursive functions

(4) first order (predicate) logic

(5) lambda calculus (the underpinnings of LISP programming language)

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ And what does it say about "Can an instruction set do everything?" \$\endgroup\$ – Transistor Apr 21 at 15:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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