Conversation

Notices

1. Adrian Cochrane (alcinnz@floss.social)'s status on Tuesday, 23-Jun-2020 20:26:46 UTC Adrian Cochrane

   One of Alan Turing's most famous discoveries is "Turing Completeness", which speaks to how broadly applicable computers can be.

   The argument ultimately relys on intuition to argue his hypothetical machine can infact define "every possible algorithm", but the independant discovery by Haskell Curry strengthened the case.

   It was Curry shortly after who coined the term "Turing Machine", as both men wrote addendums to their papers arguing that the others' ideas were equivalent.

   1/2

   • Adonay Felipe Nogueira repeated this.
   • Adrian Cochrane (alcinnz@floss.social)'s status on Tuesday, 23-Jun-2020 20:32:55 UTC Adrian Cochrane

     in reply to

     The basic theory as that as long as a computer can do these four operations it can compute just about anything:

     1. Remember data for later reuse
     2. Do different things for different data
     3. Repeat instructions
     4. Communicate to, or ideally with, people, otherwise what's the point?

     Anything else is a convenience.

     And any language/machine that provides these four operations can simulate any other machine which also satisfies them.

     2/2

     Adonay Felipe Nogueira repeated this.
   • Adrian Cochrane (alcinnz@floss.social)'s status on Tuesday, 23-Jun-2020 20:44:03 UTC Adrian Cochrane

     in reply to

     Clarification: For point one, we actually need the ability to store arbitrary ammounts of data.

     The Turing Machine used an infinitely long tape for memory, which is why we still consider hypothetical.

     Adonay Felipe Nogueira repeated this.