CogSci Computation Unit

Computation

execution of steps (algorithm) that cause functions

Algorithm

A set of steps for making an input an output

Algorithms…

calculate functions, are finitely specificable, are formally explicit

Function

A rule mapping inputs to outputs

Domain

Possible inputs to a function

Range

Possible outputs of a function

Algorithm vs. function

An algorithm gives the steps; a function describes the input-output mapping

Computational Theory of Mind (CTM)

Thinking is computation

Mentation

Mental activity, such as thinking or remembering

Mind-body problem

how the mind relates to the body; distinct from body in the way addition is distinct from a calculator

Turing machine

A theoretical machine that can compute any function and execute any algorithm and follows rules to compute

Turing Tape

The part of a Turing machine that stores symbols

Turing Cell

One space on a Turing machine's tape

Turing Finite alphabet

A limited set of symbols a machine can use

Turing Read/write head

The part that reads, erases, or writes symbols on the tape

Turing State memory

Stores the machine's current state

Turing Transition table

Instructions telling the machine what to do next

Multiple realizability

The same process can be carried out by different physical systems (Ex. chess can be played on a wood board, a plastic board, a metal board, etc.)

Church-Turing thesis

Anything computable by an algorithm can be computed by a Turing machine

Turing Machines are…

maximally powerful, maximally flexible

Maximally Powerful

a Turing Machine represents the absolute upper limit of what can be computed

Maximally Flexible

a single Turing Machine can compute anything

Universal Turing machine

A Turing machine that can simulate any other Turing machine

Difference between Turing Machine and Universal Turing Machine

A turing machine is meant to solve a specific problem. Universal Turing Machines can solve any problem.

Halting problem

The problem of determining whether a program will eventually stop running

Turing test

A test of whether a machine can appear human in conversation