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 $P_{0},P_{1},\dots$ . Sit functio $H$ ut:

H(n,x):={\begin{cases}1&P_{n}(x){\text{ consistet}}\\0&P_{n}(x){\text{ non consistet}}\end{cases}}

Si $H$ calculari posset, esset igitur programma $P$ quod eam calculat. Igitur faciamus aliud programma $Q$ , ut cuique $x$ , $Q(x)$ calculet responsum $P(x,x)$ , deinde consistat si $P(x,x)=0$ , sed sin $P(x,x)=1$ , numquam constiturum sit. Sed $Q$ est programma, est igitur $i$ ut $P_{i}$ iddem sit quod $Q$ . Sed quid respondebit $H(i,i)$ ? Si respondebit $1$ , $Q(i)$ igitur consistet, igitur $H(x,x)=0$ . Sin respondebit $0$ , $Q(i)$ igitur numquam consistet, igitur $H(x,x)=1$ . Igitur non est programma $P$ , igitur $H$ 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 $(n,x)$ ut $P_{n}(x)$ consistat, ut iam tractavimus. Hoc est nominatum quaestio consistendi.
Copia omnium sententiarum logicae primi ordinis de numeris naturalibus, nomine $\operatorname {Th} (\mathbb {N} )$ .
Porro etiam, si $T$ est theoria perfecta et congruens, quod PA (id est axiomata Peano) continet, tum $T$ calculari non poterit. Hoc est nominatum theorema prima Curtii Gödel de imperfectione, quia primum a Curtio Gödel inventum est.

Copiae RE

Sit $P$ programma. Sit copia $W:=\{n\;\vert \;P(n){\text{ consistet}}\}$ . Omnes huiusmodi copiae nominantur copiae RE (Anglice recursively enumerable, Latine "programmate numerari potens").

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

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

Hierarchia arithmetica

Sit copia $S\subseteq \mathbb {N}$ . Si $S$ calculari potest, tum semper $\phi (n)$ formulam primi ordinis fingere possumus, quod $S$ definit, id est:

S=\{n\;\vert \;\mathbb {N} \vDash \phi (n)\}

Porro autem $\phi (n)$ erit sicut $\exists x<f(n)\,\theta (x,n)$ , in quo $f$ calculari potest et $\theta (x,n)$ nullos quantificatores continet. Huiusmodi igitur formula quoque "calculari posse" dicamus, copia autem omnium formularum, quae calculari possunt, $\Delta _{0}$ nominata est, quod est imum tabulatum hierarchiae arithmeticae.

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

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

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

Gradus Turing

Si programma nostrum non tantum calculare potest, sed etiam aliquam copiam $X$ totam scit, ut semper respondere possit, utrum $n\in X$ necne, tum calculare ab copia $X$ dicitur.

Sit $X,Y$ copiae. Si $X$ ab $Y$ calculari potest, $X\leq _{T}Y$ dicitur. Si porro $Y$ ab $X$ quoque calculari potest, $X\equiv _{T}Y$ dicitur. Gradus Turing est collectio omnium copiarum, quorum alia ab alia calculari potest.

Gradus Turing vacuae copiae $0$ nominatus est, quod est gradus omnium copiarum quae calculari possunt. Si $X$ est copia, tum definiatur eius saltus $X^{\prime }$ sicut:

X^{\prime }:=\{n\;\vert \;P_{n}{\text{ consistet, quod est in serie programmatum quae calculent ab }}X\}

$0^{\prime }$ , saltus vacuae copiae, est igitur gradus copiae quaestionis consistendi, $H$ .

Theoremata amplissima

Nexus interni

Libri utiles

Nigel Cutland. Computability: An Introduction to Recursive Function Theory. ISBN 9780521294652
H.-D. Ebbinghaus, J. Flum, Wolfgang Thomas. Mathematical Logic. ISBN 9780387942582
Robert I. Soare. Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets. ISBN 9783540152996