General Computability

Source text from The Mechanical Mind by Crane

A computer is a device which processes representations in a systematic way

An algorithm is a method for calculating the value of a function

  • ”effective procedures” → procedures which, if applied correctly, are entirely effective in bringing about their results (always work)
  • Computable if the algorithm gives the value of a function for any argument
  • Church’s thesis → anything that can be executed by a Turing machine is computable
  • Conditions to be considered an algorithm
    • definite next step
    • finite number of steps

Turing Machine

The simplest possible device that could perform any computation no matter how complicated


  • Memory:
    • A long (infinitely long) tape with squares
    • A device that can write/read the symbols on the tape
    • Device can move tap one left or one right
  • Instructions:
    • Possible operations are dictated by machine’s ‘machine table’
    • A set of instructions of the form ‘if the machine is in state X and reading symbol S, then do Y and move tape right/left’

Instantiating vs Computing function

  • Instantiating → being an instance of/describable by a function
  • Computing → employs representation of input and output

Even if a person could be modeled by a Turing machine, that would not show that thinkers are computers, rather, it would show that a thinker instantiates a function, not that it computes that function.

The computational metaphor

Source: Digital Salon with Stephen Wolfram: Building a New Kind of Science, Palladium Mag

  • There is a creaking issue in universities where 70% of incoming students want to study computer science but only 5% of faculty is in computer science. What’s really going on is we want to study computer science as a proxy for the computational paradigm for everything around us
  • Is there a computable for all ?
    • Is there a computational simulation of a mind is sufficient for the actual presence of a mind?