AI, Turing test, CSP examples

Definition of AI

Artificial Intelligence is the branch of computer science that studies how to make computers perform tasks that require human intelligence, such as learning, reasoning, problem solving, perception and language understanding.

When has a machine passed the Turing Test?

In the Turing Test (Alan Turing, 1950), a human interrogator talks through text with a hidden human and a hidden machine. A machine is said to have passed the test when the interrogator, after asking questions for a fixed time, cannot reliably distinguish the machine's answers from the human's, that is, the interrogator identifies the machine correctly no better than chance (Turing predicted that by about 2000 a machine would fool an average interrogator at least 30% of the time after five minutes).

To pass, the machine needs natural language processing, knowledge representation, automated reasoning and machine learning.

Two examples of constraint satisfaction problems (CSP)

A CSP has variables, domains and constraints; a solution assigns a value to every variable so all constraints hold.

1. Map colouring: Colour the regions of a map (e.g. provinces of Nepal) with 3 colours so that no two adjacent regions have the same colour.
   • Variables: regions; Domain: {Red, Green, Blue}; Constraint: adjacent regions have different colours.
2. Cryptarithmetic puzzle (e.g. SEND + MORE = MONEY): Variables: letters; Domain: digits 0-9; Constraints: all letters get different digits, the leading letters are non-zero, and the addition is correct.

Other examples: 8-queens, Sudoku, timetable scheduling.