The Turing Machine and Test Flashcards
1
Q
Who is Alan Turing?
A
- English mathematician, logician and cryptanalyst.
- Major contributions to mathematics, cryptanalysis, logic, philosophy and also to new areas later named computer science, cognitive science and artificial intelligence.
- Set out to solve a problem posed by German mathematician David Hilbert in 1928 known as the “Entscheidungsproblem” / ”Decision-problem”: Concerned with the validity of propositions, e.g. ‘It rains when it is raining’ is TRUE, and ‘It rains when it is not raining’ is FALSE. Is there an algorithm that takes as input a statement written in formal logic, and produces a “yes” or “no” answer that is always accurate?
- Turing’s approach to solving the decision-problem: The Turing Machine.
2
Q
What is The Turing Machine?
A
- Developed by Alan Turing in 1936 while he was working on the Entscheidungsproblem.
- Theoretical computing device that can describe infinitely many operations.
3
Q
What are the components of the Turing machine?
A
- Tape / memory: Stores symbols, infinitely long, divided into an infinite number of cells. Each cell holds a character or symbol.
- Read-write head: Read, write or modify the symbols on the tape.
- Alphabet: Denotes the characters that are allowed to be written on the tape.
- Tape alphabet: Contains the characters from sigma as well as a few special symbols used in computations. These symbols mark the start position, the end position and a blank/unused cell.
- State variable: Holds a piece of information about the current state of the machine.
- Rules: Describe what the machine does given a state and the current symbol the head is reading. The rule can be to write a symbol on the tape, change the state, move the read-write head to the left of right by one spot, not move the tape, or any combination of these actions.
4
Q
What are examples of Turing Machine uses?
A
- Gave the first theoretical model for building computers.
- Still used widely in computer science as models for computation. Algorithms for solving problems can be expressed in Turing Machine languages.
- “Turing Computable”: A concept describing whether a number/function can be computed using a Turing Machine.
5
Q
How the Turing Machine work?
A
- Input is written on the tape and goes into The Turing Machine.
- The machine starts by reading the first symbol and writes a new symbol in its place in accordance to a set of rules. The rules also tell the machine in which direction to move. It follows read-write cycle over and over again until it is told to halt.
- The string written on the end of the procedure is the output and the computation is complete.
6
Q
What was the thought behind the Turing Tests?
A
- Alan Turing developed the Turing Test in 1950 for determining whether a computer is capable demonstrating human intelligence, i.e. whether a computer can think.
- Question: Can a computer talk like a human?
7
Q
Describe the Turing Test.
A
- A human judge is placed in isolation and has two text conversations with unseen players: one with a computer and one with another person. The judge evaluates the responses. The machine passes the test, if it is able to have a conversation that cannot easily be distinguished from that of a human, the machine has passed The Turing Test and has demonstrated human intelligence.
8
Q
Has any computer ever passed the Turing test?
A
No!
9
Q
What is the Turing Test a guide for?
A
Reverse-engineering the mind.
Reverse-engineering: The process of taking something apart to see how it works and trying to improve its function.
Reverse-engineering in computation: When you take neurological and anatomical data of living mechanisms to form the basis for the design of a machine.
10
Q
What is the best way to reverse-engineer something?
A
To design something that is indistinguishable.
11
Q
What is Leibniz’ Law?
A
- Leibniz’ Law (indistinguishability): Objects are identical if they have all their properties in common. Rule of ducks: If it looks like a duck, quacks like a duck, and walks like a duck, then it is a duck.
- The Turing Test is a test of functional indistinguishability.
12
Q
What is the T2 level of the Turing test?
A
T2: Limited functional mimicry
- The level at which Turing originally formulated the Turing Test.
- The functional similarity is not tied to structure.
- Restricted to symbolic interactions: symbols in, symbols out.
- Implementation-independent: Can be implemented in anything that has the capacity to run it and still pass the test.
- Example: An iPhone passes the T2 Turing test for being a duck if it is able to quack like a duck. The iPhone shares enough functionality with the duck to pass the test even though it is obvious that it is not a duck.
- Passing the T2 test for being a mind: Able do all the symbolic manipulations that a mind can do.
13
Q
What is the T3 level of the Turing test?
A
- T3: Functional identity (The Robotic Turing Test)
- The requirements for functional similarity is much higher: Functional equivalence / indistinguishability.
- The iPhone is not able to pass the T3 test because it is not functionally identical.
- However, if you design a robot duck that is functionally identical to a duck, i.e. can swim, quack etc., then it could pass the T3 Turing test even though it does not have the same biological components.
- Passing the T3 test for being a mind requires that you have a body that would meet many of the functions of a human body.
14
Q
What is the T4 level of the Turing test?
A
- The requirements from the T3 test are still relevant.
- An additional requirement has been added: structural identity.
- What does structural identity mean? The duck would have to be internally indistinguishable down to the last neuron.
- Therefore, the duck from the T3 test will not be able to pass the T4 test.
- To pass the T4 test you need a perfectly reverse-engineered duck: Structurally and functionally identical to a real duck.
15
Q
What are criticism of the Turing test?
A
- Turing machines pure symbolic computation and communication vs. the mind sensory input and motor output.
- Turing machines infinite memory capacity vs. ordinary biological systems finite memory capacity.
- Turing machines have non-addressable memory, where addressable memory would give a better model of mind.
- Turing machines operate serially rather than in parallel.
- Turing machines are deterministic, i.e. determining each computational states. But maybe it should be stochastic, i.e. not dictating a unique next state but based on probability.
