1.1.5 Intractable Problems

There are 10 types of problems covered in this section: Algorithmic, Non-Algorithmic, Finite Infinite, Computable, Non-Computable, Decidable, Undecidable, Tractable and Intractable.

Algorithmic problems are problems that can be solved a set of rules or a series of steps, kinda like a recipe for cooking. Non-Algorithmic problems are problems that can't be solved using a set of rules or some steps, they tend to be more opinion based questions, like "who would win in a fight" style questions (side note Batman always wins with sufficient planning time).

Now algorithmic problems can be divided up into 2 types (along with the initial 2) Finite and Infinite. Finite problems are problems with a finite number of inputs and are (eventually) solvable, infinite problems however have an infinite number of inputs and might be solvable or they might not.

A computable problem is a problem that can be computed, whereas non-computable ones can't be. This is because some problems can't be solved by a basic algorithm and tend to require a human to look at to see if they work or not.

A decision problem is a Yes/No algorithmic problem with any number of inputs, while a decidable problem is a decision problem with an answer eg. Is 10 divided by 5 an even number? An undecidable problem is a decision problem with no Yes/No answer eg. What's 10 divided by 5?

A tractable problem is a problem which can be solved within a reasonable amount of time (known as polynomial time) eg. organising a collection of cards. Intractable problems are problems that can't be solved withing a reasonable amount of time eg. the Traveling Salesman Problem

3.1.4 Turing Machine

In 1930 Kurt Gödel showed there are mathematical statements that could never be proved or disproved. Later Alan Turing showed that it wasn't possible to find out if a mathematical problem would be solvable or not.

Alan Turing was a British Mathematician who introduced the concept of the Turing Machine. A Turing Machine that could solve any problem that could be represented algorithimically. Using this machine he showed that it wasn't possible to determine if a pronlem had a solution or not, this means that we can never tell if a problem has a solution and we haven't put enough resourses into it or if it hasn't got a solution.

The work done by Turing is the basis from which the first computers were developed, this is shown by the fact anything a modern computer can do can be represented on a Turing Machine.

A Turing Machine has 6 components:
   1) an input alphabet
   2) an infinitely long tape
   3) an output alphabet
   4) a tape head that can read/write to the cells of the tape
   5) a finite set of states, one of whihc is the start state
   6) a set of instructions/program
Essentially it's a deterministic FSM with an infitely long tape attached.

A Turing Machine describes an algorithm and since computer programs are essentially algorithms a Turing Machine can run through and check the algortithms independant of the architecture of the machine. However as a result it's more general representation of the algorithm as when running from the machine the architecture makes decisions about how to store values which doesn't happen on the Turing Machine.

Finally Transition Rules are shorthand to show you what happens at each state of the Turing Machine:

δ(1,1)=(2,1,→) means

Transition Function(Current State (1) , Input Symbol (1)) = (Next State (2), Output Symbol (1), Movement (Right))