Fontem paginae Theoria facultatis calculandi inspicere

{{L1}}
[[Fasciculus:Recursive enumeration of all halting Turing machines.gif|thumb|Copia [[machina Turing|machinarum Turing]] quarum programmata, ''x'' quodam dato, terminant est copia RE.  Fac simulationem unius cuiusque machinae, gradatim, secundum regulam in imagine pictam.  Cum programma machinae quaedam terminet, numerum huius machinae imprime.  Ad extremum numeri omnium machinarum terminantium imprimabuntur.]]
'''Theoria facultatis calculandi''' est doctrina [[mathematica|mathematica]] de [[computatio]]ne.

==Fines theoriae==
Anno [[1936]], [[Alanus Turing]] mathematicus Anglicus librum de rebus computatoribus scripsit, ex quo theoria facultatis calculandi orta est. Quamquam, cum Turing vivebat, [[computatrum|computatra]] nondum inventa sunt, iam studens de natura computationis quaesivit, qualis functio in [[numerus naturalis|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 [[programma computatrale|programmata]] in serie countabili poni possunt, ut faciamus. Habemus igitur programmata <math>P_0,P_1,\dots</math>. Sit functio <math>H</math> ut:
:<math>H(n,x):=\begin{cases}
1 & P_n(x) \text{ consistet} \\
0 & P_n(x) \text{ non consistet}
\end{cases}</math>
Si <math>H</math> calculari posset, esset igitur programma <math>P</math> quod eam calculat. Igitur faciamus aliud programma <math>Q</math>, ut cuique <math>x</math>, <math>Q(x)</math> calculet responsum <math>P(x,x)</math>, deinde consistat si <math>P(x,x)=0</math>, sed sin <math>P(x,x)=1</math>, numquam constiturum sit. Sed <math>Q</math> est programma, est igitur <math>i</math> ut <math>P_i</math> iddem sit quod <math>Q</math>. Sed quid respondebit <math>H(i,i)</math>? Si respondebit <math>1</math>, <math>Q(i)</math> igitur consistet, igitur <math>H(x,x)=0</math>. Sin respondebit <math>0</math>, <math>Q(i)</math> igitur numquam consistet, igitur <math>H(x,x)=1</math>. Igitur non est programma <math>P</math>, igitur <math>H</math> 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 <math>(n,x)</math> ut <math>P_n(x)</math> consistat, ut iam tractavimus. Hoc est nominatum [[quaestio consistendi]].
* Copia omnium sententiarum [[logica primi ordinis|logicae primi ordinis]] de numeris naturalibus, nomine <math>\operatorname{Th}(\mathbb{N})</math>.
* Porro etiam, si <math>T</math> est [[theoria (theoria exemplarum)|theoria]] perfecta et congruens, quod PA (id est [[axiomata Peano]]) continet, tum <math>T</math> calculari non poterit. Hoc est nominatum [[theoremata Gödel de imperfectione|theorema prima Curtii Gödel de imperfectione]], quia primum a [[Curtius Gödel|Curtio Gödel]] inventum est.

===Copiae RE===
Sit <math>P</math> programma. Sit copia <math>W:=\{n\;\vert\;P(n)\text{ consistet}\}</math>. Omnes huiusmodi copiae nominantur copiae RE ([[Anglice]] ''recursively enumerable'', [[Latine]] "programmate numerari potens").

* Omnes copiae, quae calculari possint, copiae RE sunt.
* <math>H</math>, ut definvimus, est copia RE.
* Copia consequentiae axiomatum Peano, nomine <math>\operatorname{Cn}(\mathrm{PA})</math>, est copia RE.

Sed sunt tales copiae, ut <math>\operatorname{Th}(\mathbb{N})</math>, quae nec calculari possint nec copiae RE sint.

===[[Hierarchia arithmetica]]===
Sit copia <math>S\subseteq\mathbb{N}</math>. Si <math>S</math> calculari potest, tum semper <math>\phi(n)</math> formulam primi ordinis fingere possumus, quod <math>S</math> definit, id est:
:<math>S=\{n\;\vert\;\mathbb{N}\vDash\phi(n)\}</math>
Porro autem <math>\phi(n)</math> erit sicut <math>\exists x<f(n)\,\theta(x,n)</math>, in quo <math>f</math> calculari potest et <math>\theta(x,n)</math> nullos [[quantificator|quantificatores]] continet. Huiusmodi igitur formula quoque "calculari posse" dicamus, copia autem omnium formularum, quae calculari possunt, <math>\Delta_0</math> nominata est, quod est imum tabulatum hierarchiae arithmeticae.

Sit autem copia RE <math>W</math>. Semper item formula <math>\phi(n)</math> primi ordinis definita est, quae est sicut <math>\exists x\,\theta(x,n)</math>, in quo <math>\theta(x,n)</math> calculari potest. Copia omnium huiusmodi formularum nominata est <math>\Sigma^0_1</math>, quia unum tantum tabulatum quantificatorum habent. Porro semper formula <math>\psi(n)</math> primi ordinis definita est differentia <math>\mathbb{N}\backslash W</math>, quae erit sicut <math>\forall x\,\theta(x,n)</math>, in quo <math>\theta(x,n)</math> calculari potest. Copia omnium huiusmodi formularum nominata est <math>\Pi^0_1</math>.

Sit <math>i\in\mathbb{N}</math>. Sit formula <math>\phi\in\Sigma^0_i</math>. Copia omnium formularum sicut <math>\forall x\,\phi(x,n)</math> nominata est <math>\Pi^0_{i+1}</math>. Item copia omnium formularum sicut <math>\exists x\,\psi(x,n)</math>, in quo <math>\psi\in\Pi^0_i</math>, nominata est <math>\Sigma^0_{i+1}</math>. Definivimus igitur omnia tabulata hierarchiae arithmeticae.

Sunt verum copiae cui formulae nullae sint, quae eas definiunt, sicut <math>\operatorname{Th}(\mathbb{N})</math>.

===[[Gradus Turing]]===
Si programma nostrum non tantum calculare potest, sed etiam aliquam [[copia]]m <math>X</math> totam scit, ut semper respondere possit, utrum <math>n\in X</math> necne, tum calculare ab copia <math>X</math> dicitur.

Sit <math>X, Y</math> copiae. Si <math>X</math> ab <math>Y</math> calculari potest, <math>X\le_T Y</math> dicitur. Si porro <math>Y</math> ab <math>X</math> quoque calculari potest, <math>X\equiv_T Y</math> dicitur. Gradus Turing est collectio omnium copiarum, quorum alia ab alia calculari potest.

Gradus Turing vacuae copiae <math>0</math> nominatus est, quod est gradus omnium copiarum quae calculari possunt. Si <math>X</math> est copia, tum definiatur eius ''saltus'' <math>X^\prime</math> sicut:
:<math>X^\prime := \{n\;\vert\;P_n\text{ consistet, quod est in serie programmatum quae calculent ab }X\}</math>
<math>0^\prime</math>, saltus vacuae copiae, est igitur gradus copiae quaestionis consistendi, <math>H</math>.

== Theoremata amplissima ==
* [[Quaestio consistendi|Theorema de quaestione consistendi]], ab [[Alanus Turing|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]]

{{NexInt}}
* [[Algorithmus]]
* [[Fundamenta mathematicae]]
* [[Theoria exemplarum]]
* [[Theoria copiarum]]

== Libri utiles ==
* {{Cite book|author=Nigel Cutland|title=Computability: An Introduction to Recursive Function Theory|lang=en|isbn=9780521294652}}
* {{Cite book|author=H.-D. Ebbinghaus, J. Flum, Wolfgang Thomas|title=Mathematical Logic|lang=en|isbn=9780387942582}}
* {{Cite book|author=Robert I. Soare|title=Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets|lang=en|isbn=9783540152996}}

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

{{Myrias|Mathematica}}