ಗಣನಾ ಸಿದ್ಧಾಂತ

ಗಣನಾ ಸಿದ್ಧಾಂತ ಅಥವಾ ಗಣಕ ಸಿದ್ಧಾಂತ ವು ಗಣಕ ವಿಜ್ಞಾನ ಮತ್ತು ಗಣಿತಶಾಸ್ತ್ರಗಳ ಒಂದು ಭಾಗವಾಗಿದ್ದು ಕ್ರಮಾವಳಿಗಳನ್ನು ಉಪಯೋಗಿಸುವುದರ ಗಣನಾ ವಿಧಾನದ ಮೂಲಕ ಯಾವ ರೀತಿಯಲ್ಲಿ ಮತ್ತು ಎಷ್ಟು ನೈಪುಣ್ಯತೆಯಿಂದ ಸಮಸ್ಯೆಗಳನ್ನು ಪರಿಹರಿಸಬಹುದು ಎಂಬುದರ ಬಗ್ಗೆ ಬೆಳಕು ಚೆಲ್ಲುತ್ತದೆ. ಈ ಕ್ಷೇತ್ರವನ್ನು ಎರಡು ಮುಖ್ಯ ವಿಭಾಗಗಳಾಗಿ ವಿಂಗಡಿಸಲಾಗಿದೆ: ಕಂಪ್ಯೂಟೆಬಲಿಟಿ ಸಿದ್ಧಾಂತ ಮತ್ತು ಕಾಂಪ್ಲೆಕ್ಸಿಟಿ ಸಿದ್ಧಾಂತ, ಆದರೆ ಎರಡೂ ವಿಭಾಗಗಳು ಸಾಂಪ್ರದಾಯಿಕ ಕಂಪ್ಯುಟೇಷನ್ ವಿನ್ಯಾಸಗಳ ಕುರಿತಾಗಿಯೇ ಇವೆ.

ಗಣನಾವಿಧಿ(ಕಂಪ್ಯುಟೇಷನ್)ನ ಬಗ್ಗೆ ಸಮಗ್ರವಾದ ಅಧ್ಯಯನ ಮಾಡಲು ಗಣಕವಿಜ್ಞಾನಿಗಳು ಗಣಿತದ ಕಲ್ಪಿತ ರೂಪವಾದ ಗಣಕಗಳೊಡನೆ ಕೆಲಸ ಮಾಡುವರು ಮತ್ತು ಇದನ್ನು ಮಾದರಿ ಗಣನಾವಿಧಿಯೆಂದು ಕರೆಯಲಾಗುತ್ತದೆ. ಹಲವಾರು ಮಾದರಿಗಳು ಉಪಯೋಗಿಸಲಾಗುತ್ತಿವೆ, ಆದರೆ ಅತಿ ಹೆಚ್ಚು ಪರಿಶೀಲಿತವಾದುದು ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರ. ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರವು ಅಪರಿಮಿತವಾದ ಸ್ಮೃತಿಸಾಮರ್ಥ್ಯವನ್ನು ಹೊಂದಿರುವ ಡೆಸ್ಕ ಟಾಪ್ PC ಯಂರಿರುವುದೆಂದುಕೊಳ್ಳಬಹುದು, ಆದರೆ ಈ ಸ್ಮೃತಿಯನ್ನು ಇದು ಪ್ರತ್ಯೇಕವಾದ ತುಣುಕುಗಳಲ್ಲಿ ಮಾತ್ರ ಪಡೆಯಲು ಸಮರ್ಥವಾಗಿದೆ. ಗಣಕಶಾಸ್ರಜ್ಞರು ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರವನ್ನು ಅಧ್ಯಯನ ಮಾಡುವ ಕಾರಣವೇನೆಂದರೆ ಅದನ್ನು ವ್ಯವಸ್ಥಾಪಿಸಿವುದು ಸುಲಭ, ವಿಶ್ಲೇಷಿಸಬಹುದು ಮತ್ತು ಫಲಿತಾಂಶಗಳನ್ನು ಉತ್ತಮಗೊಳಿಸಲು ಬಳಸಬಹುದು, ಮತ್ತು ಅದು ಹಲವಾಉ ಜನರ ಅಭಿಪ್ರಾಯದಂತೆ ಬಹಳ ಪ್ರಬಲ, ಸಾಧ್ಯವಾಗಬಹುದಾದ, "ಯುಕ್ತವಾದ" ಕಂಪ್ಯುಟೇಷನ್ ಮಾದರಿಯನ್ನು ಪ್ರತಿನಿಧಿಸುತ್ತದೆ. ಅನಿಯಮಿತವಾದ ಸ್ಮೃತಿ ಸಾಮರ್ಥ್ಯವು ಹೊಂದಲು ಅಸಾಧ್ಯವಾದ ಗುಣಾಂಶವೆಂವೆಂದೆನಿಸಿದರೂ, ಯಾವುದೇ ತೀರ್ಮಾನಾರ್ಹ ಸಮಸ್ಯೆಯು ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರದ ಮೂಲಕ ಪರಿಹಾರಗೊಳ್ಳಲು ಬಹಳ ಕಡಿಮೆ ಸ್ಮೃತಿಯ ಅವಶ್ಯಕತೆಯಿರುತ್ತದೆ. ಆದ್ದರಿಂದ, ತಾತ್ವಿಕವಾಗಿ, ಯಾವುದೇ ಪರಿಹಾರವಾಗಬಲ್ಲ (ತೀರ್ಮಾನಾರ್ಹ) ಸಹಸ್ಯೆಯನ್ನು ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರದ ಮೂಲಕ, ಸೀಮಿತ ಸ್ಮೃತಿಯಿರುವ ಗಣಕದಿಂದ, ಬಗೆಹರಿಸಬಹುದು

ಇತಿಹಾಸ

Main article: History of theory of computation

ಕಂಪ್ಯುಟೇಷನ್ (ಗಣನಾ) ಸಿದ್ಧಾಂತವನ್ನು ಗಣಕಶಾಸ್ತ್ರದ ಕ್ಷೇತ್ರದಲ್ಲಿ ಎಲ್ಲಾ ವಿಧವಾದ ಮಾದರಿಗಳನ್ನು ಸೃಷ್ಟಿಸುವ ಸಿದ್ಧಾಂತವೆನ್ನಬಹುದು. ಆದ್ದರಿಂದ ಗಣಿತ ಮತ್ತು ತರ್ಕ ಎರಡನ್ನೂ ಬಳಸಲಾಗುತ್ತದೆ. ಕಳೆದ ಶತಮಾನದಲ್ಲಿ ಅದು ಸ್ವತಂತ್ರ ಶಿಕ್ಷಣ ವಿಷಯವೆಂದು ಪರಿಗಣಿಸಲ್ಪಟ್ಟಿತು ಮತ್ತು ಗಣಿತದಿಂದ ಬೇರ್ಪಡಿಸಲಾಯಿತು.

ಕಂಪ್ಯುಟೇಷನ್ ಸಿದ್ಧಾಂತದ ಹರಿಕಾರರೆಂದರೆ ಅಲೋನ್ಝೋ ಚರ್ಚ್, ಅಲನ್ ಟ್ಯೂರಿಂಗ್, ಸ್ಟೀಫನ್ ಕ್ಲೀನೆಲ್, ಜಾನ್ ವಾನ್ ನ್ಯೂಮನ್, ಕ್ಲಾಡ್ ಶನ್ನೋನಿ, ಮತ್ತು ನೊಆಮ್ ಚಾಮ್ಸ್ ಕಿ.

ಗಣನಾರ್ಹತಾ(ಕಂಪ್ಯೂಟೆಬಲಿಟಿ) ಸಿದ್ಧಾಂತ

Main article: Computability theory

ಗಣನಾರ್ಹತಾ ಸಿದ್ಧಾಂತವು ಮೂಲತಃ ಗಣಕದಲ್ಲಿ ಒಂದು ಸಮಸ್ಯೆಯನ್ನು ಯಾವ ಮಟ್ಟದವರೆಗೆ ಪರಿಹಾರಗೊಳಿಸಬಹುದೆಂಬುದನ್ನು ಕೈಗೆತ್ತಿಕೊಳ್ಳುತ್ತದೆ. ನಿಲ್ಲುವ ಸಮಸ್ಯೆಗಳು ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರದಿಂದ ಬಿಡಿಸಲಾಗವು ಎಂಬುದು ಗಣನಾರ್ಹತಾ ಸಿದ್ಧಾಂತದ ಪ್ರಮುಖ ಫಲಿತಾಂಶಗಳಲ್ಲಿ ಒಂದು, ಏಕೆಂದರೆ ಅದು ಒಂದು ರಚಿಸಲು ಬಹಳ ಸುಲಭವೂ, ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರದಿಂದ ಬಗೆಹರಿಸಲು ಅಸಾಧ್ಯವೂ ಆದ ಕ್ಲಿಷ್ಟವಾದ ಸಮಸ್ಯೆಗಳ ದ್ಯೋತಕವಾಗಿದೆ. ಗಣನಾರ್ಹತಾಶಾಸ್ತ್ರದ ಬಹುಭಾಗವು ನಿಲ್ಲುವ ಸಮಸ್ಯೆಯ ಫಲಿತಾಂಶದ ಆಧಾರದ ಮೇಲೆ ನಿರ್ಮಿತವಾಗಿದೆ.

ಗಣನಾರ್ಹತಾ ಸಿದ್ಧಾಂತದಲ್ಲಿ ಮತ್ತೊಂದು ಮುಖ್ಯವಾದ ಹೆಜ್ಜೆಯೆಂದರೆ ರೈಸ್ ರ ಸೂತ್ರ. ಈ ಸೂತ್ರವು ಎಲ್ಲಾ ಕ್ಷುಲ್ಲಕವಲ್ಲದ ಪಾರ್ಶ್ವ ಕ್ರಮವಿಧಿಗಳ ಗುಣವಿಶೇಷಗಳಿಗೂ, ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರ ಆ ಪಾರ್ಶ್ವ ಕ್ರಮವಿಧಿಯ ಚಿಶೇಷವನ್ನಾಧರಿಸಿಯೇ ಗಣಿಸುತ್ತದೆಯೇ ಎಂಬುದು ತೀರ್ಮಾನವಾಗಿಲ್ಲದೆ ಸಂಗತಿ ಎಂದು ಸಾರುತ್ತದೆ.

ಗಣನಾರ್ಹತಾ ಸಿದ್ಧಾಂತವು ಗಣಿತಾತ್ಮಕ ತರ್ಕದ ಒಂದು ಭಾಗಕ್ಕೆ ಸಂಬಂಧಿತವಾಗಿದ್ದು ಇದನ್ನು ರಿಕರ್ಷನ್ ಸಿದ್ಧಾಂತವೆಂದು ಕರೆಯುತ್ತಾರೆ; ಈ ಸಿದ್ಧಾಂತವನ್ನ ಬಳಸುವುದರಿಂದ ಟ್ಯೂರಿಂಗ್ ಮಾದರಿಗೆಂದು ತಗ್ಗಿಸಲ್ಪಟ್ಟ(ಆ ಹಂತಕ್ಕೆ ತರಲ್ಪಟ್ಟ) ಗಣನಾ ಮಾದರಿಗಳನ್ನು ಮಾತ್ರ ಅಧ್ಯಯನ ಮಾಡಬೇಕಾದಂತಹ ನಿರ್ಬಂಧವನ್ನು ತೆಗೆದುಹಾಕುತ್ತದೆ. ರಿಕರ್ಷನ್ ಸಿದ್ಧಾಂತವನ್ನು ಓದಿದಂತಹ ಹಲವಾರು ಗಣಿತಜ್ಞರು ಮತ್ತು ಗಣನಾ ಸಿದ್ಧಾಂತಿಗಳು ಅದನ್ನು ಗಣನಾರ್ಹತಾ ಸಿದ್ಧಾಂತವೆಂದೇ ಕರೆಯುತ್ತಾರೆ.

ಸಂಕೀರ್ಣತಾ ಸಿದ್ಧಾಂತ

Main article: Computational complexity theory

ಸಂಕೀರ್ಣತಾ ಸಿದ್ಧಾಂತವು ಯಾವುದೇ ಸಮಸ್ಯೆಯು ಗಣಕದಿಂದ ಪರಿಹಾರಗೊಳ್ಳುವಂತಹುದೇ ಎಂದು ವೀಕ್ಷಿಸುವುದಷ್ಟೇ ಅಲ್ಲದೆ ಎಷ್ಟು ಸಕ್ಷಮವಾಗಿ ಅದನ್ನು ಪರಿಹರಿಸಬಹದೆಂದೂ ವೀಕ್ಷಿಸುತ್ತದೆ. ಎರಡು ಪ್ರಮುಖ ವಿಷಯಗಳನ್ನು ಪರಿಗಣಿಸಲಾಗಿದೆ: ಕಾಲ ಸಂಕೀರ್ಣತೆ ಮತ್ತು ಕ್ಷೇತ್ರ ಸಂಕೀರ್ಂತೆ, ಎಂದರೆ ಒಂದು ಗಣನೆಯನ್ನು ಮಾಡಲು ಎಷ್ಟು ಹಂತಗಳನ್ನು ತೆಗೆದುಕೊಳ್ಳಬೇಕಾಗುತ್ತದೆ ಮತ್ತು ಅದಕ್ಕೆ ಬಾಕಾದ ಸ್ಮೃತಿ ಎಷ್ಟು ಎಂಬುದೇ ಈ ಎರಡು ವಿಷಯಗಳ ಬಗ್ಗೆಗಿನ ಜಿಜ್ಞಾಸೆ.

ದತ್ತ ಕ್ರಮಾವಳಿಯನ್ನು ಪೂರೈಸಲು ಎಷ್ಟು ಕಾಲ ಮತ್ತು ಎಷ್ಟು ಜಾಗ ಬೇಕಾಗುವುದೆಂಬುದನ್ನು ವಿಶ್ಲೇಷಿಸಲು ಗಣಕ ವಿಜ್ಞಾನಿಗಳುಸಮಸ್ಯೆಗಳನ್ನು ಬಿಡಿಸಲು ಬೇಕಾದ ಸಮಯ ಮತ್ತು ಜಾಗವನ್ನು ಹೂಡಿದ ಸಮಸ್ಯೆಗಳ ಪ್ರಮಾಣದ ಒಂದು ಕಾರ್ಯಭಾರವೆಂದು ವಿವರಿಸುತ್ತಾರೆ. ಉದಾಹರಣೆಗೆ ಒಂದು ಸಂಖ್ಯಾಪಟ್ಟಿಯಲ್ಲಿ ನಿರ್ದಿಷ್ಟವಾದ ಸಂಖ್ಯೆಯನ್ನು ಹುಡುಕುವುದು, ಪಟ್ಟಿ ಬೆಳೆದಂತೆ ಕಷ್ಟಕರವಾಗುತ್ತದೆ. ನಾವು$n$ ಸಂಖ್ಯೆಗಳು ಆ ಪಟ್ಟಿಯಲ್ಲಿವೆ ಎಂದು ಹೇಳಿದರೆ, ಮತ್ತು ಆ ಪಟ್ಟಿಯು ಅನುಕ್ರಮಣಿಕೆಯಲ್ಲಿರದಿದ್ದರೆ ಅಥವಾ ಇನ್ನಾವುದೇ ವಿಧದಲ್ಲಿ ವಿಂಗಡಿತವಾಗಿಲ್ಲದಿದ್ದರೆ, ನಾವು ಹುಡುಕುತ್ತಿರುವ ಸಂಖ್ಯೆಯನ್ನು ಪತ್ತೆಹಚ್ಚಲು ಎಲ್ಲಾ ಸಂಖ್ಯೆಗಳ ಮೇಲೂ ಕಣ್ಣಾಡಿಸಬೇಕಾಗಬಹುದು. ಆದ್ದರಿಂದ ಈ ಸಮಸ್ಯೆಯನ್ನು ಬಗೆಹರಿಸಲು ಗಣಕವು ಹಲವಾರು ಹಂತಗಳಲ್ಲಿ ಇದನ್ನು ಬಗೆ ಹರಿಸಬೇಕು ಮತ್ತು ಸಮಸ್ಯೆಯು ಎಷ್ಟು ನೀಳವಾಗಿದೆಯೋ, ಬಿಡಿಸುವ ಹಂತಗಳೂ ಅಷ್ಟೇ ನೀಳವಾಗಿರುತ್ತವೆ ಎನ್ನುತ್ತೇವೆ.

ಈ ಸಮಸ್ಯೆಯನ್ನು ಬಗೆಹರಿಸಲು ಗಣಕ ವಿಜ್ಞಾನಿಗಳು ಬಿಗ್ ೦ ನೊಟೇಷನ್ ಅಳವಡಿಸಿಕೊಂಡಿದ್ದಾರೆ; ಇದು ಕಾರ್ಯಭಾರಗಳನ್ನು ಹೋಲಿಸಲು ಯಾವ ರೀತಿ ಅನುವು ಮಾಡುವುವೆಂದರೆ, ಯಂತ್ರದ ರಚನಾರೀತಿಯ ಕೆಲವು ವಿಚಾರಗಳು ಖಂಡಿತವಾಗಿಯೂ ನಗಣ್ಯವಾಗುವಂತಾಗಿಸಿ, ಸಮಸ್ಯೆಗಳು ದೊಡ್ಡದಾದಂತೆ ಏಸಿಂಪ್ಟಾಟಿಕ್ ವರ್ತನೆಗಳನ್ನು ಮಾತ್ರ ಪರಿಶೀಲಿಸಲು ಅನುವು ಮಾಡಿಕೊಡುತ್ತದೆ. ಹೀಗಾಗಿ, ನಮ್ಮ ಹಿಂದಿನ ಉದಾಹರಣೆಯಲ್ಲಿ ಆ ಸಮಸ್ಯೆಯನ್ನು ಬಗೆಹರಿಸಲು $O(n)$ಹಂತಗಳು ಬೇಕಾಗುತ್ತವೆ ಎಂದು ಹೇಳಬಹುದು.

ಗಣಕಶಾಸ್ತ್ರದಲ್ಲಿ ಪ್ರಾಯಶಃ ಬಲು ಪ್ರಮುಖವಾದ ಬಗೆಹರಿಸಲಾಗದ ಸಮಸ್ಯೆಯೆಂದರೆ NP ಎಂದು ಸೂಚಿತವಾದ ಒಂದು ವಿಸ್ತಾರವಾದ ಶ್ರೇಣಿಯ ನಿರ್ದಿಷ್ಟ ಸಮಸ್ಯೆಯನ್ನು ಸಕ್ಷಮವಾಗಿ ಪರಿಹರಿಸಲಾಗುವುದೇ ಎಂಬ ಪ್ರಶ್ನೆ. ಮುಂದಿನ ಸಂಕೀರ್ಣತೆಯ ಶ್ರೇಣಿಗಳಾದ P ಮತ್ತು NP ಗಳಲ್ಲಿ ಇದನ್ನು ಚರ್ಚಿಸಲಾಗಿದೆ.

ಗಣನಾವಿಧಿಯ ಇತರ ಔಪಚಾರಿಕ ವ್ಯಾಖ್ಯೆಗಳು

ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರವಲ್ಲದೆ ಇತರ ಬಳಕೆಯಲ್ಲಿರುವ ಸಮಾನವಾದ (ನೋಡಿ: ಚರ್ಚ್-ಟ್ಯೂರಿಂಗ್ ಥೀಸೀಸ್) ಗಣನಾ ಮಾದರಿಗಳೆಂದರೆ;

ಲಾಂಬ್ಡಾ ಕ್ಯಾಲ್ಕುಲಸ್

ಗಣನಾವಿಧಿಯು ಒಂದು ಲಾಂಭ್ಡಾ ವಾಕ್ಯವನ್ನು (ಅಥವಾ ಎರಡು - ಕಾರ್ಯಭಾರ ಮತ್ತು ಅಳವಡಿಕೆಗಳನ್ನು ಬೇರೆಗೊಳಿಸಬೇಕಾದರೆ) ಹೊಂದಿದ್ದು, ಜೊತೆಗೆ ಒಂದು ನಿರ್ದಿಷ್ಟ ಕ್ರಮಾನುಗತವಾದ ಲಾಂಬ್ಡಾ ಪದಗಳನ್ನು - ಪ್ರತಿ ಪದವೂ ಹಿಂದಿನ ಪದದಿಂದ ಅರ್ಥಪಡೆದುದಾಗಿದ್ದು, ಒಂದು ಅನ್ವಯಿಕ ಬೀಟಾ ಇಳಿತದಲ್ಲಿ ಹೊಂದಿರುತ್ತದೆ.

ಸೇರ್ಪಡುವಿಕೆಯ ತರ್ಕ

ಒಂದು ಕಲ್ಪನೆಯಾಗಿದ್ದು $\lambda$- ಕ್ಯಾಲ್ಕುಲಸ್ ಗೆ ಬಹಳ ಹೋಲಿಕೆಯುಳ್ಳದ್ದಾದರೂ, ಪ್ರಮುಖವಾದ ವ್ಯತ್ಯಾಸಗಳು ಇವೆ(ಉದಾಹರಣೆಗೆ ನಿಶ್ಚಿತ ಬಿಂದು ಕಾಂಬಿನೇಟರ್ Y ಗೆ ಕಾಂಬಿನೇಟರಿ ತರ್ಕದಲ್ಲಿ ಸ್ವಾಭಾವಿಕ ರೂಪವಿದೆ, ಆದರೆ $\lambda$-ಕ್ಯಾಲ್ಕ್ಯುಲಸ್ ನಲ್ಲಿ ಇಲ್ಲ). ಕಾಂಬಿನೇಟರಿ ತರ್ಕವನ್ನು ಮಹತ್ವಾಕಾಂಕ್ಷೆಯಿಂದ ಅಭಿವೃದ್ಧಿಗೊಳಿಸಲಾಯಿತು:ವೈರುದ್ಧ್ಯಗಳ ರೀತಿಯನ್ನು ಅರಿಯುವುದು, ಗಣಿತದ ತಳಹದಿಯನ್ನು ಹೆಚ್ಚು ಮಿತವ್ಯಯ(ಕಲ್ಪನೆಗಳ ಬಾಬ್ತಿನಲ್ಲಿ)ವಾಗಿಸುವುದು, ಬದಲಾಗುವ ಅಂಶಗಳ ವಿಷಯವನ್ನು ಇಲ್ಲವ಻ಗಿಸುವುದು(ತನ್ಮೂಲಕ ಗಣಿತದಲ್ಲಿ ಅವುಗಳ ಪಾತ್ರವನ್ನು ಸ್ಪಷ್ಟೀಕರಿಸುವುದು) ಇದರ ಉದ್ದೇಶ.

mu-ರಿಕರ್ಸಿವ್ ಕಾರ್ಯಭಾರಗಳು

ಗಣನಾವಿಧಿಯು mu-ರಿಕರ್ಸಿವ್ ಕಾರ್ಯಭಾರ(ಎಂದರೆ ಅದರ ನಿರೂಪಣಾ ಕ್ರಮ, ಯಾವುದೆ ಅಳವಡಿಕೆಯ ಮೌಲ್ಯ(ಗಳು) ಮತ್ತು ಅಳವಡಿಕೆ ಮತ್ತು ಫಲಿತಾಂಶಗಳನ್ನು ಒಳಗೊಂಡ ಕ್ರಮಾನುಗತ ನಿರೂಪಣೆಯಲ್ಲಿ ಗೋಚರಿಸುವ ರಿಕರ್ಸಿವ್ ಕಾರ್ಯಭಾರಗಳ ಅನುಕ್ರಮಣಿಕೆ). ಆದ್ದರಿಂದ, ರಿಕರ್ಸಿವ್ ಕಾರ್ಯಭಾರದ ಕ್ರಮಾನುಗತದಲ್ಲಿ $f(x)$

ಕಾರ್ಯಭಾರಿಗಳಾದ

$g(x)$ಮತ್ತು $h(x,y)$
ಗೋಚರಿಸಿದಲ್ಲಿ, ಆಗ  'g(5)=7' ಅಥವಾ 'h(3,2)=10' ರೀತಿಯಲ್ಲಿ ವರ್ಗಗಳು ಗೋಚರಿಸಬಹುದು. ಈ ಅನುಕ್ರಮದಲ್ಲಿನ ಪ್ರತಿ ಅಂಕಿತವೂ ಒಂದು ಬೇಸಿಕ್ ಫಂಕ್ಷನ್ ನ ಅನ್ವಯಿಕವಾಗಿಬೇಕು ಅಥವಾ ಅದರ ಮೇಲಿನ ಇತರ ಅಂಕಿತಗಳನ್ನು, ಕಾಂಪೊಸಿಷನ್(ಸಂಕಲನ), ಪ್ರಿಮಿಟಿವ್ ರಿಕರ್ಷನ್, ಅಥವಾ mu-ರಿಕರ್ಷನ್ ಗಳನ್ನು ಅನುಸರಿಸಬೆಕು.  ಉದಾಹರಣೆಗೆ $f(x)=h(x,g(x))$ಆದರೆ, ಆಗ  'f(5)=3' ಗೋಚರಿಸಬೇಕಾದರೆ,  'g(5)=6' ರೀತಿಯ ಆವರ್ತನೆಗಳು ಮತ್ತು  'h(5,6)=3' ರೀತಿಯ ಆವರ್ತನೆಗಳು ಮೇಲೆ ಕಾಣಿಸಿಕೊಳ್ಳಲೇಬೇಕು. ಈ ಗಣನಾವಿಧಿಯು ರಿಕರ್ಸಿವ್ ಕಾರ್ಯಭಾರ ಅನ್ವಯಿತ ಅಳವಡಿಕೆಗಳ ಮೌಲ್ಯವನ್ನು ಕಡೆಯ ಸಂಖ್ಯೆಯು  ನೀಡಿದ ನಂತರವೇ ಮುಕ್ತಾಯಗೊಳ್ಳುತ್ತದೆ.

ಮಾರ್ಕೋವ್ ಕ್ರಮಾವಳಿ

ತಂತು ಮರುಲೇಖನ ಕ್ರಮವಾಗಿದ್ದು ವ್ಯಾಕರಣ-ಮಾದರಿಯ ನಿಯಮಗಳನ್ನನುಸರಿಸಿ ಚಿಹ್ನೆಗಳ ತಂತುಗಳ ಮೆಲೆ ಕಾರ್ಯವೆಸಗುತ್ತದೆ.

ನೋಂದಣಿ ಯಂತ್ರ

ಇದು ಸೈದ್ಧಾಂತಿಕವಾಗಿ ಗಣಕದ ಒಂದು ಕುತೂಹಲಕಾರಿ ಕಲ್ಪಿತ ರೂಪವಾಗಿದೆ. ಇದರ ಹಲವಾರು ರೂಪಗಳಿವೆ. ಅವುಗಳಲ್ಲಿ ಬಹಳ ರೂಪಗಳಲ್ಲಿ, ಪ್ರತಿ ಕಡತವು ಒಂದು ಸ್ವಾಭಾವಿಕಸಂಖ್ಯೆ(ಅನಿಯಮಿತ ಪ್ರಮಾಣದ್ದು)ಯನ್ನು ಹೊಂದಬಲ್ಲದ್ದಾಗಿದೆ, ಮತ್ತು ನಿರ್ದೇಶಗಳು ಸರಳ(ಮತ್ತು ಕೆಲವೇ) ಾಗಿರುತ್ತವೆ; ಉದಾಹರಣೆಗೆ ಕೇವಲ ದಸ್ತಾವೇಜುಕರಣ (ನಿಗದಿತ ಜಿಗಿತದೊಂದಿಗೆ) ಮತ್ತು ಬಡ್ತಿ ಕೊಡುವಿಕೆ ಮಾತ್ರ (ಮತ್ತು ನಿಲ್ಲಿಸುವಿಕೆ) ಇರುತ್ತವೆ. ಅಗಣಿತ(ಅಥವಾ ಕ್ರಿಯಾತ್ಮಕವಾಗಿ ಬೆಳೆಯುವ) ಬಾಹ್ಯ ಸಂಗ್ರಹ(ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರಗಳಲ್ಲಿ ಕಂಡುಬರುವ)ದ ಕೊರತೆಯನ್ನು ಗೋಡೆಲ್ ನಂಬರಿಂಗ್ ಕ್ರಮಗಳಲ್ಲಿನ ಅದರ ಪಾತ್ರವನ್ನು ಬದಲಾಯಿಸುವುದರ ಮೂಲಕ ಅರಿಯಬಹುದು: ಪ್ರತಿ ಕಡತದಲ್ಲೂ ಒಂದು ಸ್ವಾಭಾವಿಕ ಸಂಖ್ಯೆ ಇರುವುದರಿಂದ ಸಂಕೀರ್ಣ ವಿಷಯ(ಉದಾಹರಣೆಗೆ ಒಂದು ಅನುಕ್ರಮಣಿಕೆ, ಅಥವಾ ಒಂದು ಮ್ಯಾಟ್ರಿಕ್ಸ್, ಇತ್ಯಾದಿಗಳು)ವನ್ನು ಒಂದು ಸೂಕ್ತವಾದ ದೊಡ್ಡ ಸ್ವಾಭಾವಿಕ ಸಂಖ್ಯೆಯ ಮೂಲಕ ಪ್ರತಿನಿಧಿಸುವ ಸಾಧ್ಯತೆಯಿರುತ್ತದೆ - ಪ್ರತಿನಿಧಿಸುವಲ್ಲಿ ಮತ್ತು ಅರ್ಥೈಸುವುದರಲ್ಲಿ ಸ್ಪಷ್ಟತೆಯನ್ನು ಈ ಕ್ರಮಗಳ ಸಂಖ್ಯಾ ಸಿದ್ಧಾಂತ ತಳಹದಿಗಳಿಂದ ಅರಿಯಬಹುದಾಗಿದೆ.

P′′

ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರಗಳಂತೆಯೇ P′′ ಒಂದು ಅಗಣಿತ ಚಿಹ್ನೆಗಳ ಟೇಪ್ ಅನ್ನು(ಅನಿರ್ಬಂಧಿತ ತಲುಪುವಿಕೆಯ ಸೌಕರ್ಯವಿಲ್ಲದೆ) ಮತ್ತು ಸಾದೃಶ್ಯವಾಗಿ ಕನಿಷ್ಠ ನಿರ್ದೇಶಗಳ ಜೊತೆಯನ್ನು ಹೊಂದಿರುತ್ತದೆ. ಆದರೆ ಈ ನಿರ್ದೇಶಗಳು ಬಹಳವೇ ಅನ್ಯವಿಧದವಾಗಿದ್ದು, ಟ್ಯೂರಿಂಗ್ ಯಂತ್ರಗಳಂತಲ್ಲದೆ, P′′ ಒಂದು ನಿರ್ದಿಷ್ಟ ಸ್ಥಿತಿಗೆ ಬದ್ಧವಾಗಿರಬೇಕಿಲ್ಲ, ಏಕೆಂದರೆ ಸಕಲ "ಸ್ಮೃತಿ-ರೀತ್ಯಾ" ಕಾರ್ಯಭಾರಗಳನ್ನು ಟೇಪ್ ಮಾತ್ರ ಕೊಡಬಹುದು. ಪ್ರಸ್ತುತ ಚಿಹ್ನೆಗಳನ್ನು ಮರುಲೇಖಿಸುವ ಬದಲು, ಅದರ ಮೇಲೆ ಸಂಖ್ಯಾವಿಧಿಯ ನಿಯಮಿತ ಗುಣಕ ಬಡ್ತೀಕರಣವನ್ನು ಅದರ ಮೇಲೆಯೇ ಮಾಡಬಲ್ಲುದು. P′′ ಆವರ್ತನೆಗೂ ಒಂದು ಜೊತೆ ನಿರ್ದೇಶಗಳನ್ನು ಹೊಂದಿದ್ದು, ಶೂನ್ಯ ಚಿಹ್ನೆಗಳನ್ನು ಪರೀಕ್ಷಿಸಲು ಸಹಾಯಕವಾಗುತ್ತದೆ. ಅದು ಸಣ್ಣ ವಿಧದಲ್ಲೇ ಇದ್ದರೂ ಸಹ,ಬ್ರೈನ್ ಫಕ್ ಎಂಬ ಕ್ರಮವಿಧಿಭಾಷೆಯನ್ನು ಅಳವಡಿಸಲು ಮತ್ತು(ಮನರಂಜನೆಗಾಗಿ)ಬಳಸಲು ಅದು ಭಾಷೆಯ ಸಾಂಪ್ರದಾಯಿಕ ಜನಕವಾಗಿದೆ.

ಸಾಮಾನ್ಯ ಗಣನಾ ಮಾದರಿಗಳ ಜೊತೆಗೆ ಕೆಲವು ಸರಳವಾದ ಗಣಿಸುವಂತಹ ಮಾದರಿಗಳು ಸಹ ವಿಶೇಷ, ನಿಷೇಧಿತ ಅನ್ವಯಿಕಗಳಿಗೆ ಉಪಯುಕ್ತವಾಗಿದೆ. ಉದಾಹರಣೆಗೆ, ಕ್ರಮಬದ್ಧ ಉಚ್ಚಾರಗಳು ಅಫೀಸ್ ಅಭಿವೃದ್ಧಿಕಾರಕ ತಂತ್ರಾಂಶದಿಂದ ಹಿಡಿದು ಕ್ರಮವಿಧಿ ಭಾಷೆಗಳವರೆಗೆ ಹಲವಾರು ಸಂದರ್ಭಗಳಲ್ಲಿ ತಂತುಗಳ ರೀತಿಯನ್ನು ಸೂಚಿಸುತ್ತವೆ. ಫೈನೈಟ್ ಆಟೋಮ್ಯಾಟ್ ಎಂಬ ಮತ್ತೊಂದು ಗಣಿತರೀತ್ಯಾ ಔಪಚಾರಿಕತೆಯು ಕ್ರಮಬದ್ಧ ಉಚ್ಚಾರಗಳಿಗೆ ಸಮನಾಗಿದ್ದು, ವರ್ತುಲ ವಿನ್ಯಾಸವನ್ನು ಮತ್ತು ಕೆಲವು ವಿಧದ ಸಮಸ್ಯಾ-ಪರಿಹಾರಗಳನ್ನು ನೀಡಲು ಬಳಸಲಾಗುತ್ತದೆ. ಸಂದರ್ಭಾತೀತ ವ್ಯಾಕರಣಗಳು ಕ್ರಮವಿಧಿ ಭಾಷೆಯ ಭಾಷಾನಿಯಮಗಳನ್ನು ನಿಖರವಾಗಿ ಸೂಚಿಸುತ್ತವೆ. ನಿರ್ಧಾರಹೀನ ಪುಷ್ ಡೌನ್ ಆಟೋಮ್ಯಾಟಾ ಸಂದರ್ಭಾತೀತ ವ್ಯಾಕರಣಕ್ಕೆ ಸಮನಾದ ಮತ್ತೊಂದು ಔಪಚಾರಿಕತೆ. ಹಳೆಯ ಕಾಲದ ರಿಕರ್ಸಿವ್ ಕಾರ್ಯಭಾರಗಳು ನಿರೂಪಿತ ರಿಕರ್ಸಿವ್ ಕಾರ್ಯಭಾರಗಳ ಉಪಶ್ರೇಣಿಗಳಾಗಿವೆ.

ಗಣನಾವಿಧಿಯ ವಿವಿಧ ಮಾದರಿಗಳು ವಿವಿಧ ಕಾರ್ಯಗಳನ್ನು ನಡೆಸಲು ಸಮರ್ಥವಾಗಿವೆ. ಗಣನಾವಿಧಿಯ ಮಾದರಿಯನ್ನು ಅಳೆಯುವ ಒಂದು ವಿಧವೆಂದರೆ ಆ ಮಾದರಿಯು ಉತ್ಪಾದಿಸಬಲ್ಲ ಔಪಚಾರಿಕ ಭಾಷೆಗಳ ಶ್ರೇಣಿಯನ್ನು ಅಧ್ಯಯನ ಮಾಡುವುದು; ಭಾಷಾ ಚಾಂಸ್ಕಿ ಹೈರಾರ್ಕಿ(ಶ್ರೇಷ್ಠ ಪರಂಪರೆ)ಯು ದೊರೆಯುವ ವಿಧದಲ್ಲಿ ಈ ಅಧ್ಯಯನವು ಸಾಗಬೇಕು.

ಗಣನಾವಿಧಿಯ ಸೈದ್ಧಾಂತಿಕ ಬುನಾದಿ

ಗಣನಾವಿಧಿಯು ಯಾವಯಾವುದನ್ನು ಒಳಗೊಂಡಿದೆ ಎಂದು ಒಂದು ವಿಸ್ತೃತ ದೃಷ್ಟಿ ಬೀರಿದರೆ ಔಪಚಾರಿಕ ಶಬ್ದಾರ್ಥನಿರ್ವಚನಶಾಸ್ತ್ರ ಮತ್ತು ಗಣನಾ ತರ್ಕದಂತಹ ವಿಷಯಗಳನ್ನು ಹೊಂದಿರುವುದು ಕಂಡುಬಂದು, ಸಮಾನಾಂತರ ಗಣನಾವಿಧಿ, ನ್ಯೂರಲ್ ನೆಟ್ ವರ್ಕ್ ಮತ್ತು ಪ್ರಮಾಣ ಗಣನಾಕ್ರಿಯೆ (ಕ್ವಾಂಟಂ ಕಂಪ್ಯೂಟಿಂಗ್)ಗಳಂತಹ ವಿಷಯಗಳ ಸೈದ್ಧಾಂತಿಕ ವಿಚಾರಗಳು ಒಳಗೊಂಡಿರುವುದ ಸ್ಪಷ್ಟವಾಗುತ್ತದೆ.

ಹೆಚ್ಚಿನ ಮಾಹಿತಿಗಾಗಿ

ಕಂಪ್ಯೂಟರ್ ವಿಜ್ಞಾನಿಗಳಿಗೆಂದೇ ಇರುವ ಪಠ್ಯಪುಸ್ತಕಗಳು

(ಈ ಕ್ಷೇತ್ರದಲ್ಲಿ ಬಹಳ ಪಠ್ಯಪುಸ್ತಕಗಳಿವೆ; ಹಾಗಾಗಿ ಇದು ಐಚ್ಛಿಕವಾಗಿಯೇ ಅಪೂರ್ಣ.)

• ಹಾಪ್ ಕ್ರಾಫ್ಟ್, ಜಾನ್ ಇ., ಮತ್ತು ಜೆಫ್ರೀ ಡಿ.ಉಲ್ಮನ್, (2006). ಇಂಟ್ರೊಡಕ್ಷನ್ ಟು ಆಟೋಮ್ಯಾಟಾ ಥಿಯರಿ, ಲ್ಯಾಂಗ್ವೇಜಸ್ ಎಂಡ್ ಕಂಪ್ಯುಟೇಷನ್ . ಮೂರನೆಯ ಆವೃತ್ತಿ , ರೀಡಿಂಗ್, MA:ಅಡಿಸನ್-ವೆಸ್ಲೀ. ISBN 978-0321455369 ಈ ಕ್ಷೇತ್ರದ ಆಕರಗ್ರಂಥಗಳಲ್ಲೊಂದು.
• Michael Sipser (2006). Introduction to the Theory of Computation 2ed. PWS Publishing. ISBN 0-534-94728-X.
• Eitan Gurari (1989). An Introduction to the Theory of Computation. Computer Science Press. ISBN 0-7167-8182-4. {{cite book}}: External link in |title= (help)
• ಹೀಯ್ನ್, ಜೇಮ್ಸ್ ಎಲ್. (1996) ಥಿಯರಿ ಆಫ್ ಕಂಪ್ಯುಟೇಷನ್. ಸಡ್ಬರಿ, MA: ಜೋನ್ಸ್ & ಬಾರ್ಟ್ ಲೆಟ್. ISBN 978-0867204971 ಈ ಕ್ಷೇತ್ರಕ್ಕೆ ಒಂದು ಹದವಾದ ಪರಿಚು, ಪದವಿಪೂರ್ವ ಎರಡನೆಯ ವರ್ಷದ ಗಣಕಶಾಸ್ತ್ರ ವಿದ್ಯಾರ್ಥಿಗಳಿಗೆ ಸೂಕ್ತವಾದುದು.
• ಟೈಲರ್ ಆರ್. ಗ್ರೆಗೊರಿ(1998). ಮಾಡಲ್ಸ್ ಆಫ್ ಕಂಪ್ಯುಟೇಷನ್ ಎಂಡ್ ಫಾರ್ಮಲ್ ಲ್ಯಾಂಗ್ವೇಜಸ್. ನ್ಯೂಯಾರ್ಕ್: ಆಕ್ಸ್‌ಫರ್ಡ್ ಯುನಿವರ್ಸಿಟಿ ಪ್ರೆಸ್. ISBN 978-0195109832 ಒಂದು ಅಪರೂಪಕ್ಕೆ ಓದಬಲ್ಲಂತಹ ಪಠ್ಯಪುಸ್ತಕ,

ಉನ್ನತಮಟ್ಟದ ಪದವಿಪೂರ್ವ ಹಾಗೂ ಪದವಿ ಆರಂಭಿಕ ವರ್ಷದ ವಿದ್ಯಾರ್ಥಿಗಳಿಗೆ.

• ಲೂಯಿಸ್ ಎಫ್.ಡಿ. (2007). ಎಸೆನ್ಷಿಯಲ್ಸ್ ಆಫ್ ಥಿಯರೆಟಿಕಲ್ ಕಂಪ್ಯೂಟರ್ ಸೈನ್ಸ್ ವಿಧಿಯುಕ್ತ ಭಾಷೆಗಳ, ಸ್ವಯಂಚಾಲನೆಯ ವಿಷಯಗಳ ಮತ್ತು ವ್ಯಾಕರಣ ವಿಷಯಗಳ ಬಗ್ಗೆ ಮಾಹಿತಿಗಳನ್ನು ಹೊಂದಿರುವ ಪಠ್ಯಪುಸ್ತಕ. ಫಲಿತಾಂಶಗಳ ಕುರಿತು ಪುರಾವೆಗಳನ್ನು ನೀಡುವುದಕ್ಕಿಂತಲೂ, ಫಲಿತಾಂಶಗಳ ಮತ್ತು ಅವುಗಳ ಅನ್ವಯಿಕಗಳ ಒಂದು ಸ್ಥೂಲನೋಟ ಬೀರುವುದೇ ಈ ಪುಸ್ತಕದ ಮುಖ್ಯ ಉದ್ದೇಶದಂತಿದೆ.
• ಮಾರ್ಟಿನ್ ಡೇವಿಸ್, ರಾನ್ ಸಿಗಾಲ್, ಎಲೇಯ್ನ್ ಜೆ ವೆಯೂಕರ್, ಕಂಪ್ಯೂಟೆನಿಲಿಟಿ, ಕಾಂಪ್ಲೆಕ್ಸಿಟಿ ಎಂಡ್ ಲ್ಯಾಂಗ್ವೇಜಸ್: ಫಂಡಮೆಂಟಲ್ಸ್ ಆಫ್ ಥಿಯರೆಟಿಕಲ್ ಕಂಪ್ಯೂಟರ್ ಸೈನ್ಸ್, ಎರಡನೆಯ ಆವೃತ್ತಿ, ಅಕಾಡೆಮಿ ಪ್ರೆಸ್, 1994. ISBN 0122063821. ಬಹಳಷ್ಟು ಪರಿಚಯಾತ್ಮಕ ಪುಸ್ತಕಗಳಿಗಿಂತಲೂ ಹೆಚ್ಚು ವಿಷಯಗಳನ್ನು ವ್ಯಾಪಕವಾಗಿ ನೀಡಿದೆ; ಪ್ರೋಗ್ರಾಂ ಸೆಮಾಂಟಿಕ್ಸ್ ಮತ್ತು ಕ್ವಾಂಟಿಫಿಕೇಷನ್ ಸಿದ್ಧಾಂತವನ್ನು ಸಹ ಒಳಗೊಂಡಿದೆ. ಪದವಿ ವಿದ್ಯಾರ್ಥಿಗಳಿಗಾಗಿ ಬರೆಯಲಾಗಿದೆ.

(ವಿಸ್ತೃತವಾದ)ಗಣಿತದ ದೃಷ್ಟಿಯಲ್ಲಿ ಗಣನಾರ್ಹತಾ ಸಿದ್ಧಾಂತದ ಬಗೆಗಿನ ಪುಸ್ತಕಗಳು

ಹಾರ್ಟ್ಲೇ ರೋಜರ್ಸ್, ಜೂನಿಯರ್ (1987). ಥಿಯರಿ ಆಫ್ ರಿಕರ್ಸಿವ್ ಎಂಡ್ ಎಫೆಕ್ಟಿವ್ ಕಂಪ್ಯೂಟೆಬಿಲಿಟಿ , MIT ಪ್ರೆಸ್. ISBN 0-762-42739-6

• S. Barry Cooper (2004). Computability Theory. Chapman and Hall/CRC. ISBN 1-58488-237-9..
• ಕಾರ್ಲ್ ಸ್ಮಿತ್, ಎ ರಿಕರ್ಸಿವ್ ಇಂಟ್ರೊಡಕ್ಷನ್ ಟು ದ ಥಿಯರಿ ಆಫ್ ಕಂಪ್ಯುಟೇಷನ್ , ಸ್ಪ್ರಿಂಗರ್, 1994,ISBN 0387943323. ಗಣಕಶಾಸ್ತ್ರ ವಿಭಾಗದ ಪದವಿ ವಿದ್ಯಾರ್ಥಿಗಳಿಗೆ ಸೂಕ್ತವಾದಂತಹ ಚಿಕ್ಕದಾದ ಪಠ್ಯಪುಸ್ತಕ.

ಐತಿಹಾಸಿಕ ದೃಷ್ಟಿಕೋನದಿಂದ

• Richard L. Epstein and Walter A. Carnielli (2000). Computability: Computable Functions, Logic, and the Foundations of Mathematics, with Computability: A Timeline (2nd ed.). Wadsworth/Thomson Learning. ISBN 0-534-54644-7..

ಇವನ್ನೂ ನೋಡಿ

ಸೈದ್ಧಾಂತಿಕ ಗಣಕ ವಿಜ್ಞಾನ

ಬಾಹ್ಯ ಕೊಂಡಿಗಳು

• ಕಂಪ್ಯೂಟೆಬಿಲಿಟಿ ಲಾಜಿಕ್ Archived 2011-04-11 ವೇಬ್ಯಾಕ್ ಮೆಷಿನ್ ನಲ್ಲಿ. - ಎ ಥಿಯರಿ ಆಫ್ ಇಂಟರಾಕ್ಟಿವ್ ಕಂಪ್ಯುಟೇಷನ್. ಈ ವಿಷಯದ ಬಗ್ಗೆ ಪ್ರಮುಖ ಜಾಲ ಆಕರ.