# Computability

Mind Map by Carla Fernanda E, updated more than 1 year ago
 Created by Carla Fernanda E about 6 years ago
6
0

Lectura

## Resource summary

Computability
1. A problem is computable if it can be solved by some algorithm; a problem that is noncomputable cannot be solved by any algorithm.
1. Halting Problem,
1. Alan Turing
1. The way to show that uncomputable problems exist is to find one, similarly to the way G¨odel showed unprovable true statements exist by finding an unprovable true statement.
1. A convincing proof requires a formal model of computing. This is why Alan Turing developed a model of computation.
2. Perhaps there is a procedure in some more powerful programming language in which it is possible to implement a solution to the Halting Problem. In fact, we will see that no more powerful programming language exists.
1. Proved that noncomputable problems exist.
2. Mechanizing Reasoning
1. Aristotle’s Organon developed rules of inference known as syllogisms to codify syllogisms logical deductions in approximately 350 BC.
1. Euclid -> axiomatic system, a formal system consisting of a set of axioms and a set of in- axiomatic system ference rules to codify knowledge in some domain.
1. five axioms (more commonly known as postulates),five common notions,, 468 propositions
1. A proof of a proposition in an axiomatic systemis a sequence of steps that ends with the proposition.
2. A consistent axiomatic system is one that can never derive contradictory statements by starting from the axioms and following the inference rules.
1. A complete axiomatic system can derive all true statements by starting from the axioms and following the inference rules. This means if a given proposition is true, some proof for that proposition can be found in the system.
1. Bertrand Russell discovered a problem with Frege’s system, which is now known as Russell’s paradox.
1. In 1913, Whitehead and Russell published Principia Mathematica
1. Godel showed that no powerful axiomatic system could be both complete and consistent:
1. no matter what the axiomatic system is, if it is powerful enough to express a notion of proof, it must also be the case that there exist statements that can be expressed in the system but cannot be proven either true or false within the system.
1. Godel established that no interesting and consistent axiomatic system is capable of proving all true statements in the system
1. are there problems for which no procedure exists that produces the correct output for every possible problem instance in a finite amount of time??
1. problem: A description of an input and a desired output. procedure: A specification of a series of actions. algorithm: A procedure that is guaranteed to always terminate.
2. a bold attempt to mechanize mathematical reasoning

### Similar

ALAN MATHISON TURING
2Cognición humana TURING
Alan Turing
ALÁN TURING
ALAN TURING
Máquina de Turing
DATA
ALAN TURING
2Cognición humana TURING
IB Economics SL: Macroeconomics
Compensation and Benefits PHR Study Guide