Theoria facultatis calculandi

Theoria facultatis calculandi est doctrina mathematica de computatione.

Fines theoriae
Anno 1936, Alanus Turing mathematicus Anglicus librum de rebus computatoribus scripsit, ex quo theoria facultatis calculandi orta est. Quamquam, cum Turing vivebat, computatra nondum inventa sunt, iam studens de natura computationis quaesivit, qualis functio in numeris naturalibus manu calculari possit. Id est, functio cui algorithmus dari possit, quem, si quis mechanice et nulla intelligentia consequitur, omnia responsa illius functionis scire potuerit.

Turing exemplum in suo libro dedit functionis, quae calculari non potest. Sit automaton calculandi universale, ut machina Turing. Huius automatonis programmata in serie countabili poni possunt, ut faciamus. Habemus igitur programmata . Sit functio  ut:

Si  calculari posset, esset igitur programma  quod eam calculat. Igitur faciamus aliud programma , ut cuique ,  calculet responsum , deinde consistat si , sed sin , numquam constiturum sit. Sed  est programma, est igitur  ut  iddem sit quod . Sed quid respondebit ? Si respondebit ,  igitur consistet, igitur . Sin respondebit ,  igitur numquam consistet, igitur . Igitur non est programma , igitur  non calculari potest, quod erat demonstrandum.

Definitiones et exempla
Facultas calculandi
Sit functio vel copia. Calculari potest, si quid programmatis automati calculandi est, quod eam functionem vel indicantem functionem eius copiae calculet. Multa autem sunt automata calculandi, sed omnia automata calculandi quae satis valent, inter se potentia eadem sunt, id quod est Thesis Church-Turing. Nobis igitur tantum "calculari posse" dicendum est, quod talibus automatis calculari posse significat.

Multae enim functiones vel copiae, quas calculare cupiamus, non possunt calculari. Hic sunt exempla:
 Copia omnium  ut  consistat, ut iam tractavimus. Hoc est nominatum quaestio consistendi.
 Copia omnium sententiarum logicae primi ordinis de numeris naturalibus, nomine .
 Porro etiam, si  est theoria perfecta et congruens, quod PA (id est axiomata Peano) continet, tum  calculari non poterit. Hoc est nominatum theorema prima Curtii Gödel de imperfectione, quia primum a Curtio Gödel inventum est.

Copiae RE
Sit  programma. Sit copia . Omnes huiusmodi copiae nominantur copiae RE (Anglice recursively enumerable, Latine "programmate numerari potens").

 Omnes copiae, quae calculari possint, copiae RE sunt.
 , ut definvimus, est copia RE.
 Copia consequentiae axiomatum Peano, nomine , est copia RE.

Sed sunt tales copiae, ut , quae nec calculari possint nec copiae RE sint.

Hierarchia arithmetica
Sit copia . Si  calculari potest, tum semper  formulam primi ordinis fingere possumus, quod  definit, id est:

Porro autem  erit sicut , in quo  calculari potest et  nullos quantificatores continet. Huiusmodi igitur formula quoque "calculari posse" dicamus, copia autem omnium formularum, quae calculari possunt,  nominata est, quod est imum tabulatum hierarchiae arithmeticae.

Sit autem copia RE . Semper item formula  primi ordinis definita est, quae est sicut , in quo  calculari potest. Copia omnium huiusmodi formularum nominata est , quia unum tantum tabulatum quantificatorum habent. Porro semper formula  primi ordinis definita est differentia , quae erit sicut , in quo  calculari potest. Copia omnium huiusmodi formularum nominata est .

Sit . Sit formula . Copia omnium formularum sicut  nominata est . Item copia omnium formularum sicut , in quo , nominata est . Definivimus igitur omnia tabulata hierarchiae arithmeticae.

Sunt verum copiae cui formulae nullae sint, quae eas definiunt, sicut .

Gradus Turing
Si programma nostrum non tantum calculare potest, sed etiam aliquam copiam  totam scit, ut semper respondere possit, utrum  necne, tum calculare ab copia  dicitur.

Sit  copiae. Si  ab  calculari potest,  dicitur. Si porro  ab  quoque calculari potest,  dicitur. Gradus Turing est collectio omnium copiarum, quorum alia ab alia calculari potest.

Gradus Turing vacuae copiae  nominatus est, quod est gradus omnium copiarum quae calculari possunt. Si  est copia, tum definiatur eius saltus  sicut:

, saltus vacuae copiae, est igitur gradus copiae quaestionis consistendi, .

 Theoremata amplissima 
 Theorema de quaestione consistendi, ab Alano Turing inventa.
 Theorema Tarski de defectu definitionis
 Theoremata Gödel de imperfectione
 Theoremata Kleene de puncto immobili
 Theorema Kleene-Post
 Theorema Friedberg-Muchnik
 Theorema Posner-Robinson

 Algorithmus
 Fundamenta mathematicae
 Theoria exemplarum
 Theoria copiarum

 Libri utiles 




Categoria:Logica
Categoria:Mathematica
Categoria:Scientia computatralis
Categoria:Alanus Mathison Turing