9. Automata and Computers
9.1. The Computational Theory of Mind
Cognitive science founding disciplines :
Psychology
Linguistics
Philosophy of mind
Neurosciences
Computer science (Cybernetics + AI)
Could a machine think? Could the mind itself be a machine?
Computers were designed to simulate the mental operations realized by a human mathematician performing a… computation (see Alan Turing)
The Computational Theory of Mind has been defended and attacked many times.
More readings:
Zylberberg, Ariel, Stanislas Dehaene, Pieter R. Roelfsema, and Mariano Sigman. 2011. “The Human Turing Machine: A Neural Framework for Mental Programs.” Trends in Cognitive Sciences
Van Gelder, Tim. 1995. “What Might Cognition Be, If Not Computation?:” Journal of Philosophy 92 (7): 345–81.
Jerry Fodor The Mind does not work that way
Douglas Hoftstader Gödel, Escher & Bach: an eternal golden braid and I am a strange loop
9.2. What is computation anyway ?
One common answer is:
“Computation is what a Turing machine can do”
But what is a Turing machine?
9.3. The ancestors of the computer: the automata
An automaton is a device designed to automatically follow a predetermined sequence of operations.
(see Descartes’ Les Animaux Machines Lettre au Marquis de Newcastle
9.4. Formal description of an automaton
At a abstract level, an automaton can be formally described by:
a set of internal states
a transition table (or diagram) that describes the events that lead to changes from one state to the other state.
9.5. Examples of transition diagrams
A Finite State Automaton can be used to generate or recognize regular languages.
In Formal Language Theory, a language is a set of strings.
Examples:
{ a, aa, ab, ba, aab, bab, …}
{ ha!, haha!, hahaha!, hahahaha!, …}
{ ab, aabb, aaabbb, … }
{ the set of grammatical English sentences}
9.6. What is a Computer?
A computer is basically an automaton augmented with a memory store.
This is particularly clear in the case of the Turing machine, a mathematical model of computation (Turing offered the Turing machine as an analysis of the activity of an (idealised) human mathematician engaged in computing).
A Turing machine is a finite state machine augmented with a tape and a mechanism to read/write on it.
Read Roger Penrose’s chapter’s on Turing machines and https://en.wikipedia.org/wiki/Turing_machine. You may laos read the Alan Turing’s seminal paper.
Other computing machines have been invented, yet:
“All attempts to give an exact analysis of the intuitive notion of an effectively calculable function have turned out to be equivalent, in the sense that each analysis offered has been proved to pick out the same class of functions, namely those that are computable by Turing machine.
The concept of effective calculability has turned out to be formalism-independent, in that all these different formalisms pick out exactly the same class of functions.” (B. Jack Copeland “The Church-Turing thesis” in Stanford Encyclopedia of Philosophy Archive)
Another computing model which is closer to actual computers, is the register machine.
9.7. Register machines
Read The seven secrets of computer power revealed (Chapter 24 from Daniel Dennett’s Intuition Pumps and other tools for thinking)
The RogRego computer possesses:
a bank of registers, or memory locations, each with a unique address (1, 2, 3, …), and each able to have, as content, a single integer (0, 1, 2, …)
a processing unit can execute instructions in a stepwise, one-at-a-time fashion. The processor knows only 3 instructions:
End: finishes the programs
- Increment register with 2 arguments:
a register number to increment by 1
a step (line) number to jump to when the increment is complete
- Decrement register and Branch with 3 arguments:
a register number to decrement by 1
a step number to jump if the register contains a non null value.
a step number to jump if the register contains 0
An online demo is available at http://proto.atech.tufts.edu/RodRego/
You can enter the following program “ADD[0,1]”, on a machine where Reg0 contains 4 and Reg1 contains 7. Try to explain what it is doing:
1 DEB 0 2 3
2 INC 1 1
3 END
…
This program adds the content of register 0 to register 1 (destroying the content of 0)
…
Exercice: write a program Program 2 “MOVE[4,5]” that moves the content of reg4 intro reg5
…
1 DEB 5 1 2
2 DEB 4 3 4
3 INC 5 2
4 END
…
Program 3 “COPY[1,3]” copies the content of reg1 into reg3, leaving reg1 unchanged:
1 DEB 3 1 2
2 DEB 4 2 3
3 DEB 1 4 6
4 INC 3 5
5 INC 4 3
6 DEB 4 7 8
7 INC 1 6
8 END
Program 4 (NON DESTRUCTIVE ADD[1,2,3]):
1 DEB 3 1 2
2 DEB 4 2 3
3 DEB 1 4 6
4 INC 3 5
5 INC 4 3
6 DEB 4 7 8
7 INC 1 6
8 DEB 2 9 11
9 INC 3 10
10 INC 4 11
11 DEB 4 12 13
12 INC 2 11
13 END
…
Note that conditional branching is the key instruction that gives the power to the machine. Depending on the content of memory, the machine can do either (a) or (b).
9.7.1. Exercice: implementation of a Register machine
Write a Python script that simulates a RodRego machine with 10 registers. The program is stored in a string or in file that is read and then executed. Your program must contain a function which, given the 10 initial values of the registers, and the program, returns the new register values when the END command is reached.
Check two possible solutions:
- rodrego_maxime_caute.py
- rodrego_christophe_pallier.py
—
9.8. The Seven secrets of computers revealed
Competence without comprehension. A machine can do perfect arithmetic without having to comprehend what it is doing.
What a number in a register stands for depends on the program
The register machine can be designed to discriminate any pattern that can be encoded with numbers (e.g. figures, text, sensory inputs,…)
Programs can be encoded by numbers.
All programs can be given a unique number which can be treated as a list of instructions by a Universal Machine.
all improvements in computers over Turing machine (or Register machine), are simply ways of making them faster
There is no secret #7
9.9. Programmable computers
The first computers were not programmable. They were hardwired!
An important milestone was the invention of the programmable computer:
a program is a set of instructions stored in memory.
Loaded and executed by a processor.
Such programs are written in machine langage (the language of the processor)
9.10. Compilation and interpretation
Programs written in higher=level languages (rather than Machine language) can be either:
= compiled, or = interpreted
In both cases, you write the program as text files called source files.
A compiler translates the program into an executable file in machine language. The executable file is standalone, that is, the source code is not needed.
An interpreter reads the file and execute the commands one by one. It is slower, but easier to interact with. Disatvantage: you need the interpreter to exectute it.
9.11. Operating systems
In the first computers, there was only one program running. One would load the program into memory, then run it until it halted. Several Programs were ran in batch mode, in a sequence.
Then, it was realized that computers could time-share between programs, allowing several users (or programs) to share the computer.
This requires an operating systems (O.S.). The O.S. is the first program that loads into the computer during the boot. When running:
The OS controls the hardware (screen/printer/disk/keybord/mouse,…) (drivers)
The OS manages all the other programs (processes/tasks/applications).
sharing memory
allocating processors and cores
allocating time
Check out Task Manager (Windows)/System Monitor (Linux)/ Activity Monitor (Mac)
Different OSes offer different “views” of the computer (e.g. 1 button mouse in Mac, 2 in Windows, 3 in Linux), so often programs are designed to work on one OS (bad!). Prefer multiplatform software (like Python).
Several OS can be installed in a given machine:
choice at boot (multiboot)
an OS can run inside a virtual machine, that is a program running in another (or the same) OS, and emulating a full computer.
9.12. What is a Terminal?
Terminal (or console): originaly, a device comprising a keyboard and screen, allowing a human to interact with a computer.
Remarks:
Before keyboards and screens, there were punchcards and printers:
Historically, terminals used to be a dumb screen/keyboard connected to a central computer.
In the mainframe era, many terminals were connected to a single, powerful, computer. Everybody was sharing the same computer
With the advent of Personal Computers, the terminal and the computer became a single apparatus.
However, terminals can be virtual. A terminal is a program that let you run text programs. You interact by typing and displaying text. No graphical interface/no mouse.
When you open a terminal, a program called a shell is started that displays a prompt, waiting for you to enter commands with the keyboard.