Artificial Intelligence Overview

Artificial Intelligence (AI)

• AI is the science of making computers perform tasks that require intelligence when performed by humans.
• Multiple definitions exist for AI.

Distinction between AI and Human

• Computers outperform humans in terms of speed and accuracy.
• Computers struggle with unforeseen situations and their performance deteriorates rapidly.
• Humans struggle with complex computations but possess reasoning and intuitive abilities.
• Humans are more likely to comprehend results and determine subsequent computations.

AI - Different Perspectives

• Many definitions focus on thought process, reasoning, and behavior.
• Thinking like humans: Achieving this through introspection (analyzing one's own thoughts) and psychological experience.
• Acting like humans: This involves areas such as natural language processing, knowledge representation, automated reasoning, and machine learning.
• Thinking rationally: Aiming for systems driven by logic and deduction allowing them to solve problems by applying logical rules to a description of the problem.
• Acting rationally: Systems are deemed rational when they perform the correct actions.

The Turing Test

• Developed by Alan M. Turing, the test evaluates machine intelligence.
• It involves an interrogator, a human respondent, and a machine to be tested.
• The interrogator aims to discern if the machine or the human is providing responses.
• Turing's test focuses on the machine's ability to fool the interrogator into believing it is a human.

Agent

• An agent is a device that responds to stimuli from its environment, similar to a robot.
• Agents have sensors for receiving data, and actuators for interacting with the environment.

Functions

• A relationship between possible input and output values where each input has a single output.
• Computing a function means determining output from input.
• A non-computable function is one that cannot be solved by any algorithm.

Turing Machine

• Has a tape, a read/write head, and a state register.
• Uses instructions to read, write, and move the head.
• Each step uses the state and tape value as input.

Incrementing a Value

• Turing Machine reads tape, changes state, writes the incremented value, and moves the head.
• Uses a specific set of states and instructions to achieve the task.

Church-Turing Thesis

• States that any problem solvable by Turing Machine is also solvable by an algorithm and vice versa.

Universal Programming Language

• Can be used to express any computable function.
• Examples include Bare Bones and popular programming languages.

Bare Bones Language

• A simple but universal language.
• Uses statements like clear name, incr name, decr name, and while name not 0 do.

The Halting Problem

• Given any program's encoded version, determine if it will terminate or not.
• This problem is unsolvable, meaning no algorithm can solve it for every case.

Public-Key Cryptography

• Uses key values for encryption and decryption.
• Public keys are used for encryption, while private keys are for decryption.
• RSA is a popular algorithm that relies on the assumed difficulty of factoring large numbers.

Encryption via Knapsack Problem

• Selects numbers from a set to add up to a target value.
• Encrypts messages by breaking them into segments, representing each segment as a number, and then selecting values from a list to get a sum that represents the segment.
• The process involves encoding messages with a specific set of numbers, making it tough for an unauthorized person to decode without the key.

Easy & Hard Knapsack Problems

• Easy Knapsack: Each number is larger than the sum of the preceding numbers, making decoding relatively simple.
• Hard Knapsack: Utilizes three magic numbers for encryption. It creates a list of numbers by multiplying a set of numbers with a magic number, then taking the remainders after dividing by another magic number.

Modular Arithmetic

• Replaces integers with their remainders after division by a fixed value, known as the modulus.
• Two numbers that leave the same remainder when divided by a modulus are considered equivalent modulo that number.
• Essential in cryptography for building secure encryption methods.

Encryption Process in the Hard Knapsack Problem

• The process involves a modulus ‘m’ and multiplicative inverses ‘x’ and ‘y’ in modulo ‘m’.
• Encrypted messages are decoded using modular arithmetic, which relies on these specific numbers for decryption.