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.

\$\endgroup\$
2
  • \$\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\$ Apr 21, 2020 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\$ Apr 21, 2020 at 16:24

3 Answers 3

8
\$\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.

\$\endgroup\$
0
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.

\$\endgroup\$
2
  • \$\begingroup\$ "Arduino is not an instruction set." - I know. \$\endgroup\$
    – Noob_Guy
    Apr 23, 2020 at 14:28
  • 1
    \$\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, 2020 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)

\$\endgroup\$
1
  • 1
    \$\begingroup\$ And what does it say about "Can an instruction set do everything?" \$\endgroup\$
    – Transistor
    Apr 21, 2020 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.