Cog Sci - Module 6 - Representations and Algorithms

Computational Theory of Mind 

• Cognition is computations performed over representations

• Different representations mean different algorithms 

• Many algorithms for one output- but there are tradeoffs. 
  

History of Computation

• All strides in Computer Science/led to making of the first computer 

History of Computation - 1800-1600 BCE

Babylonian algorithm for the length of a diagonal 

History of Computation - 200-100 BCE 

• Antikythera mechanism calculates astronomical events 

History of Computation - 1804

• Joseph Jacquard patents an automatic weaving machine 

History of Computation - 1822

• Charles Babbage builds a model of his difference engine 

History of Computation - 1843

• Ada Lovelace writes first computer program 

Ada Lovelace 

• Considered to write the very first computer program 

• She speculated that the very first computational machine would be able to do even more than Charles Babbage’s machine 

• Lays foundation for thinking about general AI, unlimited machine that is self fueled

History of Computation - 1936

• Alonzo Church and Alan Turing simultaneously write proofs that first-order logic is undecidable 

• Lambda calc 

• Find out if something is true or false 

The Halting Problem 

• Give a program some input. Will the program finish running, or will it run forever? 

• Can a general algorithm solve this problem for any program-input pair?

this question led to the Turing machine 

Decidability 

• If there is one algorithm that can answer the question: halt or not, for every program and every possible answer to this program - no 

• The answer is no, the problem is undecidable 

• In trying to understand decidability- he found this problem 

• Interdisciplinary work is important - decidability problem - posed by david turing  

Undecidability

no decision whether it will come up w an output or keep going for ever and ever 

Levels of analysis for turing machine - lego video

• Of turing machine in action, but lego version 

Levels of analysis in it

• Computational: they way it solves 2+2= there is different ways and tradeoffs to solving it 

• Algorithmic: solving 2 + 2 

• Implementational: made of lego 

Turing machine ingredients

• An infinite tape 

• A read/write head 

  • Sensor reading what is on the tape, can write something/override whats on the tape 

• An alphabet of symbols 

  • Can think of as 0s and 1s 

  • A set of instructions (the machine table)

    • algorithm/set of steps that must be taken and the rules those steps must follow

Turing machine doesn’t actually exist?

• bc we need an infinitely 

long tape

• Turing machine should be able to compute a mind, computationalism, and computational theory of mind - mind is just a computer + anything that is computable, the turing machine can compute 

how to do turing machine computation

• read current state 

• read current symbol 

• match to instructions on machine table

(leave the same or change whatever needs to be changed) 

Turing machine similarity to human computation

Ex:  when you see something you say it 

• Comes out of your mouth 

• But there are steps in between that, visual processing, other stuff, language 

Turing Machine - characteristics

• Foundation for all modern computing 

• Can solve any math problem ever

• + Not limited to math 

• Any algorithm that is going to be computed 

Automaticity

• There’s no external operator calling the shots 

• can run by itself, without human operation 

Determinacy 

Behavior is determined entirely by the current state and symb

Turing’s impact 

• The Turing Machine formalized algorithms and is the basis for all modern computing. Addressing problem that turned into modern computer system. 

• Turing has been influential not just for computer science, but for cognitive science as a whole 

  • Formalisms and way of representing algorithms are way of representing formalism - what minds do and how they solve problems 

Computability - Church turing thesis

• Church - lambda calc , 

• Turing - studies the turing machine- came up w it 

Church- “No computational procedure will be algorithm unless it can be representing as a Turing Machine” 

• Everything your mind does is computation 

• Every computation should be able to be solved by turing machine 

• Turing -  “A function is effectively calculable if its values can be found by some purely mechanical process.” 

Artificial intelligence 

• A Turing machine is a symbolic processor that can compute anything.

• Does this mean everything a human mind can do, a Turing Machine can do? 

• Can man-made computers have minds? 
  

• Mental computations are not only exercisable by the human brain 

Describe the Turing machine and explain its impact on cognitive science.

• Theoretical machine with a infinitely long tape 

• Foundation for all modern computing

• Can solve any math problem and not limited to math

• Any algorithm that is going to be computed

• Turing machine formalized algorithms and is the basis for all modern computing 

  • Formalisms and way of representing algorithms are ways of representing formalism - what minds do and how they solve problems

What is the Church-Turing thesis, and what are its implications?

• “No computational procedure will be considered as algorithm unless it can be represented as a Turing machine” - Church

  • Everything your mind does is computation

  • Every computation should be able to be solved by Turing Machine

• “A function is effectively calculable if its values can be found by some purely mechanical process” - Turing 

Describe the Turing test and explain what it is meant to do.

• A test for intelligence in a computer

• A human should be unable to tell the machine from another human by using the replies to questions given to both

Explain the Frame Problem as a challenge for artificial intelligence.

• Challenge of how AI system keeps track of what changes and what stays the same after a action is preformed

• AI may assume everything may change - confusion and inefficient

• Or may struggle to keep accurate, up to date understanding of the world

• Problem of knowledge representation and reasoning efficiency 

Describe the Searle’s Room argument and explain its implications for computational theory of mind.

• Argues that symbol manipulation is not enough to characterize the mind

• Computational theory of mind - mind functions like computer 

• Someone can sort symbols of chinese, may seem like they know chinese but its just symbol manipulation

• Computers do not necessarily understand language or have true intelligence

Describe the Complexity Problem. How does it relate to the Church/Turing thesis?

• Even if computer can solve problem, it may take too long or need too much memory to solve - hard for AI to solve complex tasks quickly

• Church turing - any problem that can be solved using step by step can be solved by turing machine - but does not say how fast

• Church turing tells us what can be computed, complexity problem tells us what cant be computed easily

Turing machine

What it is: A mathematical model of computation

Why it was invented: To prove the undecidability of the halting problem

Why we care in cog sci: It provides a precise definition of computation and computability 

Multiple realizability + church turing thesis

1 - Systems with minds are cognitive systems 

2 - Cognitive systems are computational systems

3 - Turing machines can completely describe any computational system 

4 - Therefore, Turing machines can completely describe any cognitive system 

5 - Turing machines are defined independently of implementation. 

6 - Therefore, cognitive systems can be defined independently of implementation 

7 - Therefore, systems with minds can be defined independently of implementation 

Turing Test

• human questioner asks a series of questions to both respondents. After the specified time, the questioner tries to decide which terminal is operated by the human respondent and which terminal is operated by the computer

Human needs to tell the difference between whether they are talking to a human or a computer 

• If you cant tell that backs up the idea that a computer has a mind 

Relevance

decision, action making, having a conversation with each other

• humans have unique reasoning and relevance skills, we know what is relevant vs not to a problem

• We don’t know how we understand relevance, but we do

The frame problem

How can we represent the effects of an action? 

Problem: the set of possible effects and non effects is immense!

AI/computers challenge of representing how actions affect the world without having to explicitly state all the things that don’t change

Searle’s room

• Room where person goes in and arranges words to mean different things, based on a book of what these symbols mean 

• They get an input sentence and produce an output sentence, despite not knowing what these symbols/words mean. 

• Is symbol manipulation sufficient to characterize the mind? 

Mental representations have ———- properties

• Mental representations have semantic properties - they have meaning 

Searle’s room asks - Can you have a mind without meaning?  

The complexity problem

How complex cognitive systems solve problems

• An algorithm designed for a physical system can only be run by another physical system with the addition of an emulator 

• Not only the case it is the same software, there is something else we need to add 
  

• The increase in computational complexity can affect behavior
  

Ex: Friend or Foe 

• 2 computers faced with same problem- there is a magnet which will block signal 

Althon Alan - starts to perform the behavior but magnet stops it 

Intel Alan- tries to implement behavior in different way, but magnet soon stops it

Implementation and physical level differences are intertwined

• Implementational level differences - will effect whether we can perform the behavior or not 

  • We wont even be able to see whether it was doing function 

Physical stuff - makes a difference in which computation things perform

Theory 

is crucial to interpretation 

Empirical limits of church turing thesis

Uninformative 

• It is both too easy and too hard to find the same functions in different physical systems 

Untestable 

• We can’t implement just one functional description 

• If we wanna test if something does a function we have to look at a lot more stuff than one functional description 

Frame problem ex:

Ex: 

A robot was programmed to know its battery would soon run out 

• It made a plan to go to the room to get battery- which was on a wagon 

• When it pulled the battery out, it also triggered a bomb 

• It did not consider the side effects of its action

Ex 2: 

R1D1 (another robot) - was able to consider side effects of actions 

• Thought pulling something out (the battery) would effect the colors of the walls 

• Humans wouldn’t care about that/ we know it doesn’t matter