According to the Church-Turing thesis,
computable functions are exactly the functions that can be calculated using a mechanical calculation device given unlimited amounts
of time and storage space.
[
enCOMPUTABLE_FUNCTION ]
This leads to
computable variants of AC and AP, and Universal "Levin" Search (US) solves all inversion problems in optimal (apart from some unrealistically
large multiplicative constant) time.
[
enALGOWIKI ]
To show that a problem is not
computable, we need to show that no algorithm exists that solves the problem.
[
enCOMPUTABILITY12 ]
francés
calculable
MCLH GC AMG
05/07/2015
|