Universality of Computation and Algorithms Flashcards
Hilbert’s program
a proposed solution to the foundational crisis of mathematics, when early attempts to clarify the foundations of mathematics were found to suffer from paradoxes and inconsistencies. Attempted to formalise mathematics as a finite set of axioms
Hilbert’s program consistency
Means that mathematics could have no paradoxes
Hilbert’s program completeness
Every true statement would be provable
Hilbert’s program decidability
We can tell whether or not a statement is provable
Godel’s incompleteness theorem
Created in response to Hilbert’s program
- if arithmetic is consistent, there can always be true statements that cannot be proven using a finite set of axioms
- it is not possible for any proof based upon the set of axioms to demonstrate the consistency of the axioms
Turing machine
Can hypothetically action and execute any algorithm regardless of the complexity. It is also used as the basis for determining the computational complexity of a problem given an efficient algorithm.
Church Turing Thesis
Describes the concept of computability:
The Turing machine can compute any problem that is computable.
- For every solvable decision problem, it can be transformed into an equivalent Turing machine problem
- If a problem can be solved by a Turing machine, it is then considered computable
Cobham’s thesis
For something to be feasibly computable, it has to be computable in polynomial time O(n^k), but not O(k^n)
Halting problem
An unsolvable and undecidable problem, proven using a contradiction. Determines whether an algorithm will halt or loop forever
DNA Computing
When components of problems are encoded as physical DNA sequences, which can be combined to create sequences that represent all possible solutions, allowing for parallel computing. DNA amount increases exponentially with input size
Chinese Room Argument
Proposed in response to Turing Test, where a native English speaker is in a room with Chinese characters and instructions (program). If the instructions contained every possible input, the person in the room could pass the Turing test without any Chinese knowledge. Can AI understand what it is doing or is it just following instructions?
Neural Networks
Calibrating computer to learn, using supervised learning and user training (captcha test). Giving inputs “this is a bus” and checking outputs, used for image and speech recognition, which can vary in input but still result in the same output
Basic Neural Network Graph
input hidden layer output
O ———— O ————- O
w1
(refer to 2017 q7 c for a proper graph lol)
