ನಿರ್ಣಯ ಪ್ರಶ್ನೆ
From Wikipedia
ಗಣಿತವನ್ನು ಗಣಿತದ ಮೂಲಕವೇ ನಿರೂಪಿಸಬಹುದೆ? "ನಿರ್ಣಯ ಪ್ರಶ್ನೆ" (decision problem) ಇಂಥದೆ ಒಂದು ಪ್ರಶ್ನೆ ನಮ್ಮೆ ಮುಂದಿಡುತ್ತದೆ.
೧೯೦೦ ರಲ್ಲಿ ಜೆರ್ಮನಿಯ ಡೆವಿಡ್ ಹಿಲ್ಬೆರ್ಟ್ ಎಂಬ ಗಣಿತ ಶಾಸ್ತ್ರಜ್ನ ಇತರ ಗಣಿತರಿಗೆ ಮುಂದಿಟ್ಟ ಒಂದಿಶ್ಟು ಮೂಲಭೂತ ಸಮಸ್ಯೆ ಗಳ ಪೈಕಿ ಈ "ನಿರ್ಣಯ ಪ್ರಶ್ನೆ"ಯೂ ಒಂದು. ಈ ಪ್ರಶ್ನೆಯ ರೂಪಣೆ ಈ ರೀತಿ ಇದೆ:
ಯಾವುದೆ ಒಂದು ಗಣ (set) U ದಿಂದ ನಾವು ಎಷ್ಟೋ ರೀತಿಯ ಉಪಗಣಗಳನ್ನು (subset) ನಿರ್ಮಿಸಬಹುದು. ಈ ರೀತಿ ಯಾವುದೇ ಒಂದು ಉಪಗಣ A ಅನ್ನು ನಿರ್ಮಿಸಿದಾಗ, ಗಣ U ನಲ್ಲಿರುವ ಪ್ರತಿಒಂದು ಸದಸ್ಯ ವಸ್ತುವಿಗೆ ಒಂದು A-ಸದಸ್ಯತ್ವದ ಒಂದು ನಿರ್ಣಾಯಕ ಪ್ರಶ್ನೆಯನ್ನು ನಿರೂಪಿಸಬಹುದು.
ಉದಾಹರಣೆಗೆ, U = {0,1,2,3,4,5,6,7,8,...} ಎಂಬ ಅಂಕಿಗಳ ಗಣವಾದರೆ, ಇದರಿಂದ A = {0,2,4,6,8,...} ಎಂಬ ಸ್ಮಸಂಖ್ಯೆಗಳ ಉಪಗಣವನ್ನು ನಿರೂಪಿಸಬಹುದು. ಹೀಗೆ ಉಪಗಣವನ್ನು ನಿರ್ಮಿಸಿದಾಗ, U ನಲ್ಲಿರುವ ಪ್ರತಿಯೊಂದು ಸದಸ್ಯ ಅಂಕಿಗೂ ಒಂದು A-ಸದಸ್ಯತ್ವದ ಪ್ರಶ್ನೆಯನ್ನು ಕೇಳಬಹುದು. ಈ ಪ್ರಶ್ನೆಗೆ "ಹೌದು" (೧) ಅಥವ "ಇಲ್ಲ" (೦) ಮಾತ್ರ ಉತ್ತರಗಳು. ಉದಾಹರಣೆಗೆ U-ಸದಸ್ಯ 2ಕ್ಕೆ, A-ಸದಸ್ಯತ್ವದ ಉತ್ತರ "ಹೌದು" ಎಂದು, ಮತ್ತು U-ಸದಸ್ಯ 11ಕ್ಕೆ, A-ಸದಸ್ಯತ್ವದ ಉತ್ತರ "ಇಲ್ಲ" ಎಂದು.
ಈ ಮೇಲ್ಕಂಡ ಉದಾಹರಣೆಯಲ್ಲಿ, ಸದಸ್ಯತ್ವದ ಪ್ರಶ್ನೆಯನ್ನು ಗಣಿತದ ಮೂಲಕ ಉತ್ತರಿಸುವುದು ಸರಾಗ. ಯಾವುದೆ ಒಂದು U-ಸದಸ್ಯವನ್ನು, 2 ರಿಂದ ಭಾಗಿಸಲು ಸಾಧ್ಯವಾದಲ್ಲಿ, ನಮ್ಮ ಉತ್ತರ "ಹೌದು" ಇಲ್ಲವೆ, "ಇಲ್ಲ."
ಆದರೆ, ಗಣ U ದಿಂದ ಯಾವುದೇ ಒಂದು ರೀತಿಯಲ್ಲಿ ನಿರೂಪಿಸಿದ ಉಪಗಣ A ಗೆ ಈ ರೀತಿಯ ಸದಸ್ಯತ್ವದ ಪ್ರಶ್ನೆಯನ್ನು ಗಣಿತದ ಮೂಲಕ ಉತ್ತರಿಸಬಹುದೆ? ಇದೇ ನಿರ್ಣಯ ಪ್ರಶ್ನೆ.
ನಿರ್ಣಯ ಪ್ರಶ್ನೆಯನ್ನು ಉತ್ತರಿಸಲು ಅಸಾಧ್ಯ ಎಂಬುದು ಈಗ ನಿರೂಪಣೆಯಾಗಿದೆ. ಗಣಕಯಂತ್ರ ಶಾಸ್ತ್ರದಲ್ಲಿ ಇದು ಒಂದು ಪ್ರಮುಖವಾದ ನಿರೂಪಣೆ. ಈ ಅಸಾಧ್ಯತೆ ಯನ್ನು ಹಲವರು ನೀರೂಪಿಸಿದರು. ಇವರಲ್ಲಿ ಕುರ್ಟ್ ಗೊಡೆಲ್, ಬೆರ್ಟ್ರಾಂಡ್ ರಸ್ಸೆಲ್, ಆಲೊಂಜೋ ಚರ್ಚ್ ಮತ್ತು ಅಲೆನ್ ಟ್ಯೂರಿಂಗ್ ಪ್ರಮುಖರು.
ಗಣಿತದ ಪ್ರಾಕಾರ, ನಾವು ಕೇಳಬಹುದಾದಂತ ಯಾವುದೇ ಪ್ರಶ್ನೆಯನ್ನು ಮೂಲಭೂತವಾಗಿ ಒಂದು ರೀತಿಯ ಗಣ ಸದಸ್ಯತ್ವದ ನಿರ್ಣಯ ಪ್ರಶ್ನೆ ಯಂತೆ ರೂಪಿಸಬಹುದು. ನಿರ್ಣಯ ಪ್ರಶ್ನೆಯನ್ನು ಉತ್ತರಿಸಲ್ಲು ಸಾಧ್ಯವಾಗಿದ್ದಲ್ಲಿ, ನಮಗೆ ತೋರುವ ಯಾವುದೇ ಪ್ರಶ್ನೆಯನ್ನು ಗಣಿತದ ಮೂಲಕ ಉತ್ತರಿಸಬಹುದು ಎಂದಾಗುತ್ತಿತ್ತು!
