Theoria facultatis calculandi

E Vicipaedia
Salire ad: navigationem, quaerere
Copia 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 de computatione.

Fines theoriae[recensere | fontem recensere]

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, qui 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[recensere | fontem recensere]

Facultas calculandi[recensere | fontem recensere]

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:

Copiae RE[recensere | fontem recensere]

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[recensere | fontem recensere]

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^0_1, 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^0_1.

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

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

Gradus Turing[recensere | fontem recensere]

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\le_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[recensere | fontem recensere]

Vide etiam[recensere | fontem recensere]

Libri utiles[recensere | fontem recensere]

  • 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 


Roman numeral 10000 CC DD.svg