Majority problem
ಬಹುಮತದ ಸಮಸ್ಯೆ, ಅಥವಾ ಸಾಂದ್ರತೆಯ ವರ್ಗೀಕರಣ ಕಾರ್ಯವು, ಬಹುಮತದ ಮತದಾನವನ್ನು ನಿಖರವಾಗಿ ನಿರ್ವಹಿಸುವ ಒಂದು ಆಯಾಮದ ಸೆಲ್ಯುಲಾರ್ ಆಟೋಮ್ಯಾಟನ್ ನಿಯಮಗಳನ್ನು ಕಂಡುಹಿಡಿಯುವ ಸಮಸ್ಯೆಯಾಗಿದೆ. ಸ್ಥಳೀಯ ಪರಿವರ್ತನೆಯ ನಿಯಮಗಳನ್ನು ಬಳಸಿಕೊಂಡು, ಜೀವಕೋಶಗಳು ವ್ಯವಸ್ಥೆಯಲ್ಲಿರುವ ಎಲ್ಲಾ ಜೀವಕೋಶಗಳ ಒಟ್ಟು ಸಂಖ್ಯೆಯನ್ನು ತಿಳಿಯಲು ಸಾಧ್ಯವಿಲ್ಲ. ಒಂದರ ಸಂಖ್ಯೆಯನ್ನು ಎಣಿಸಲು (ಅಥವಾ, ಸಮ್ಮಿತಿಯಿಂದ, ಸೊನ್ನೆಗಳ ಸಂಖ್ಯೆ), ವ್ಯವಸ್ಥೆಯು ವ್ಯವಸ್ಥೆಯ ಒಟ್ಟು ಗಾತ್ರದಲ್ಲಿ ಬಿಟ್ಗಳ ಲಾಗರಿದಮಿಕ್ ಸಂಖ್ಯೆಯನ್ನು ಬಯಸುತ್ತದೆ. ವ್ಯವಸ್ಥೆಯ ಗಾತ್ರದಲ್ಲಿ ರೇಖಾತ್ಮಕವಾದ ದೂರದಲ್ಲಿ ಸಂದೇಶಗಳನ್ನು ಕಳುಹಿಸಲು ಮತ್ತು ವ್ಯವಸ್ಥೆಯು ನಿಯಮಿತವಲ್ಲದ ಭಾಷೆಯನ್ನು ಗುರುತಿಸಲು ಸಹ ಇದು ಅಗತ್ಯವಾಗಿರುತ್ತದೆ. ಹೀಗಾಗಿ, ಸೆಲ್ಯುಲಾರ್ ಆಟೋಮ್ಯಾಟನ್ ವ್ಯವಸ್ಥೆಗಳ ಕಂಪ್ಯೂಟೇಶನಲ್ ಶಕ್ತಿಯನ್ನು ಅಳೆಯುವಲ್ಲಿ ಈ ಸಮಸ್ಯೆಯು ಒಂದು ಪ್ರಮುಖ ಪರೀಕ್ಷಾ ಪ್ರಕರಣವಾಗಿದೆ. ಸಮಸ್ಯೆಯ ಹೇಳಿಕೆ ಒಟ್ಟು i + j ಕೋಶಗಳನ್ನು ಹೊಂದಿರುವ ಎರಡು-ಸ್ಥಿತಿಯ ಸೆಲ್ಯುಲಾರ್ ಆಟೋಮ್ಯಾಟನ್ನ ಸಂರಚನೆಯನ್ನು ನೀಡಿದರೆ, ಅವುಗಳಲ್ಲಿ i ಶೂನ್ಯ ಸ್ಥಿತಿಯಲ್ಲಿದೆ ಮತ್ತು j ಒಂದೇ ಸ್ಥಿತಿಯಲ್ಲಿದೆ, ಮತದಾನದ ಸಮಸ್ಯೆಗೆ ಸರಿಯಾದ ಪರಿಹಾರವು ಅಂತಿಮವಾಗಿ ಎಲ್ಲಾ ಕೋಶಗಳನ್ನು ಶೂನ್ಯಕ್ಕೆ ಹೊಂದಿಸಬೇಕು i> j ಆಗಿದ್ದರೆ ಮತ್ತು ಅಂತಿಮವಾಗಿ i <j ಆಗಿದ್ದರೆ ಎಲ್ಲಾ ಕೋಶಗಳನ್ನು ಒಂದಕ್ಕೆ ಹೊಂದಿಸಬೇಕು. i = j ಆಗಿದ್ದರೆ ಅಪೇಕ್ಷಿತ ಅಂತಿಮ ಸ್ಥಿತಿಯನ್ನು ನಿರ್ದಿಷ್ಟಪಡಿಸಲಾಗುವುದಿಲ್ಲ. ಶೂನ್ಯಗಳು ಮತ್ತು ಶೂನ್ಯಗಳ ಅನುಪಾತವು 50 ಪ್ರತಿಶತಕ್ಕಿಂತ ಬೇರೆ ಯಾವುದಾದರೊ ಮಿತಿಗಿಂತ ಮೇಲಿದೆಯೇ ಅಥವಾ ಕೆಳಗಿದೆಯೇ ಎಂಬುದನ್ನು ಪರೀಕ್ಷಿಸಲು ಸಹ ಈ ಸಮಸ್ಯೆಯನ್ನು ಸಾಮಾನ್ಯೀಕರಿಸಬಹುದು. ಈ ಸಾಮಾನ್ಯೀಕರಣದಲ್ಲಿ, ಒಬ್ಬರಿಗೆ ಒಂದು ಮಿತಿಯನ್ನು ಸಹ ನೀಡಲಾಗುತ್ತದೆ; ಮತದಾನದ ಸಮಸ್ಯೆಗೆ ಸರಿಯಾದ ಪರಿಹಾರವು ಅಂತಿಮವಾಗಿ ಎಲ್ಲಾ ಕೋಶಗಳನ್ನು ಶೂನ್ಯಕ್ಕೆ ಹೊಂದಿಸಬೇಕು ಮತ್ತು ಅಂತಿಮವಾಗಿ ಎಲ್ಲಾ ಕೋಶಗಳನ್ನು ಒಂದಕ್ಕೆ ಹೊಂದಿಸಬೇಕು. ಬಯಸಿದ ಅಂತಿಮ ಸ್ಥಿತಿಯನ್ನು ನಿರ್ದಿಷ್ಟಪಡಿಸಲಾಗಿಲ್ಲ. ಅಂದಾಜು ಪರಿಹಾರಗಳಾದ ಗಾಕ್ಸ್, ಕುರ್ಡ್ಯುಮೋವ್ ಮತ್ತು ಲೆವಿನ್ ಒಂದು ಸ್ವಯಂಚಾಲಿತ ಯಂತ್ರವನ್ನು ಕಂಡುಹಿಡಿದರು, ಅದು ಯಾವಾಗಲೂ ಬಹುಪಾಲು ಸಮಸ್ಯೆಯನ್ನು ಸರಿಯಾಗಿ ಪರಿಹರಿಸದಿದ್ದರೂ, ಅನೇಕ ಸಂದರ್ಭಗಳಲ್ಲಿ ಹಾಗೆ ಮಾಡುತ್ತದೆ. ಸಮಸ್ಯೆಯ ಬಗೆಗಿನ ಅವರ ವಿಧಾನದಲ್ಲಿ, ಸೆಲ್ಯುಲಾರ್ ಆಟೋಮ್ಯಾಟನ್ ನಿಯಮದ ಗುಣಮಟ್ಟವನ್ನು ಅದು ಸರಿಯಾಗಿ ವರ್ಗೀಕರಿಸುವ ಸಂಭವನೀಯ ಆರಂಭಿಕ ಸಂರಚನೆಗಳ ಭಾಗದಿಂದ ಅಳೆಯಲಾಗುತ್ತದೆ. ಗ್ಯಾಕ್ಸ್, ಕುರ್ಡ್ಯುಮೋವ್ ಮತ್ತು ಲೆವಿನ್ ಪ್ರಸ್ತಾಪಿಸಿದ ನಿಯಮವು ಪ್ರತಿ ಜೀವಕೋಶದ ಸ್ಥಿತಿಯನ್ನು ಈ ಕೆಳಗಿನಂತೆ ಹೊಂದಿಸುತ್ತದೆ. ಒಂದು ಕೋಶವು 0 ಆಗಿದ್ದರೆ, ಅದರ ಮುಂದಿನ ಸ್ಥಿತಿಯು ತನ್ನ ಮೌಲ್ಯಗಳಲ್ಲಿ ಬಹುಮತವಾಗಿ ರೂಪುಗೊಳ್ಳುತ್ತದೆ, ಎಡಕ್ಕೆ ಅದರ ಹತ್ತಿರದ ನೆರೆಯ ಮತ್ತು ಎಡಕ್ಕೆ ಅದರ ನೆರೆಯ ಮೂರು ಸ್ಥಳಗಳು. ಮತ್ತೊಂದೆಡೆ, ಒಂದು ಕೋಶವು 1 ಆಗಿದ್ದರೆ, ಅದರ ಮುಂದಿನ ಸ್ಥಿತಿಯು ಸಮ್ಮಿತೀಯವಾಗಿ ರೂಪುಗೊಳ್ಳುತ್ತದೆ, ಅದರ ಮೌಲ್ಯಗಳಲ್ಲಿ ಬಹುಪಾಲು, ಬಲಕ್ಕೆ ಅದರ ತಕ್ಷಣದ ನೆರೆಯ ಮತ್ತು ಬಲಕ್ಕೆ ಅದರ ನೆರೆಯ ಮೂರು ಸ್ಥಳಗಳು. ಯಾದೃಚ್ಛಿಕವಾಗಿ ರಚಿಸಲಾದ ನಿದರ್ಶನಗಳಲ್ಲಿ, ಇದು ಬಹುಮತವನ್ನು ಸರಿಯಾಗಿ ನಿರ್ಧರಿಸುವಲ್ಲಿ ಸುಮಾರು ಶೇಕಡಾ 78ರಷ್ಟು ನಿಖರತೆಯನ್ನು ಸಾಧಿಸುತ್ತದೆ. ಆನುವಂಶಿಕ ಕ್ರಮಾವಳಿಗಳನ್ನು ಬಳಸಿಕೊಂಡು ಉತ್ತಮ ನಿಯಮಗಳನ್ನು ಅಭಿವೃದ್ಧಿಪಡಿಸಲು ಸಾಧ್ಯವಿದೆ ಎಂದು ದಾಸ್, ಮಿಚೆಲ್ ಮತ್ತು ಕ್ರಚ್ಫೀಲ್ಡ್ ತೋರಿಸಿದರು. 1995ರಲ್ಲಿ, ಲ್ಯಾಂಡ್ ಮತ್ತು ಬೆಲೆವ್, ಕೋಶಗಳ ಸಂಖ್ಯೆಯು ಸಾಕಷ್ಟು ದೊಡ್ಡದಾಗಿದ್ದರೆ (ಸುಮಾರು 4r/ρ ಗಿಂತ ದೊಡ್ಡದಾಗಿದ್ದರೆ) ತ್ರಿಜ್ಯ r ಮತ್ತು ಸಾಂದ್ರತೆ ρ ಹೊಂದಿರುವ ಯಾವುದೇ ಎರಡು-ಸ್ಥಿತಿ ನಿಯಮವು ಎಲ್ಲಾ ಆರಂಭಿಕ ಸಂರಚನೆಗಳಲ್ಲಿ ಮತದಾನದ ಸಮಸ್ಯೆಯನ್ನು ಸರಿಯಾಗಿ ಪರಿಹರಿಸುವುದಿಲ್ಲ ಎಂದು ತೋರಿಸಿದರು. ಈ ವ್ಯವಸ್ಥೆಯು ನಿರ್ಣಾಯಕವಾಗಿರುವುದರಿಂದ, ಸಂಪೂರ್ಣವಾಗಿ ಶೂನ್ಯಗಳಿಂದ ಅಥವಾ ಒಂದರಿಂದ ಸುತ್ತುವರೆದಿರುವ ಪ್ರತಿಯೊಂದು ಜೀವಕೋಶವೂ ನಂತರ ಶೂನ್ಯವಾಗಬೇಕು ಎಂದು ಅವರ ವಾದವು ತೋರಿಸುತ್ತದೆ. ಅಂತೆಯೇ, ಯಾವುದೇ ಪರಿಪೂರ್ಣ ನಿಯಮವು ಒಂದು ಅನುಪಾತವು ಅದಕ್ಕಿಂತ ಕೆಳಗಿದ್ದರೆ (ಅಥವಾ ಪ್ರತಿಯಾಗಿ) ಅದನ್ನು ಎಂದಿಗೂ ಹೆಚ್ಚಿಸುವುದಿಲ್ಲ. ಯಾವುದೇ ಊಹಿಸಲಾದ ಪರಿಪೂರ್ಣ ನಿಯಮವು ಅನುಪಾತವನ್ನು ತಳ್ಳಿದ ಪ್ರತ್ಯೇಕವಾದ ನಿಯಮವನ್ನು ರದ್ದುಗೊಳಿಸಲು ಕಾರಣವಾಗುತ್ತದೆ ಅಥವಾ ಅವುಗಳ ಅನುಪಾತವು ಅದಕ್ಕಿಂತ ಕಡಿಮೆಯಿದ್ದರೆ, ಪ್ರತ್ಯೇಕವಾದ ನಿಯಮವು ನಕಲಿ ನಿಯಮಗಳನ್ನು ಶೂನ್ಯಗಳ ಗುಂಪಿಗೆ ಸೇರಿಸಲು ಕಾರಣವಾಗುತ್ತದೆ ಎಂದು ಅವರು ತೋರಿಸುತ್ತಾರೆ. 2013 ರಲ್ಲಿ, ಬುಸಿಕ್, ಫ್ಯಾಟೆಸ್, ಮಾರ್ಕೋವಿಸಿ ಮತ್ತು ಮೈರೆಸ್ ಅವರು ಪರಿಪೂರ್ಣ ಸಾಂದ್ರತೆಯ ವರ್ಗೀಕರಣವನ್ನು ಹೊಂದಲು ಅಸಾಧ್ಯವೆಂದು ಸರಳವಾದ ಪುರಾವೆಯನ್ನು ನೀಡಿದರು, ಇದು ನಿರ್ಣಾಯಕ ಮತ್ತು ಯಾದೃಚ್ಛಿಕ ಸೆಲ್ಯುಲಾರ್ ಮತ್ತು ಯಾವುದೇ ಆಯಾಮ ಎರಡಕ್ಕೂ ಹೊಂದಿರುತ್ತದೆ. ಕ್ಯಾಪ್ಕರೆರೆ, ಸಿಪ್ಪರ್ ಮತ್ತು ಟೋಮಾಸ್ಸಿನಿಯವರು ಗಮನಿಸಿದಂತೆ, ಸ್ವಯಂಚಾಲಿತ ಯಂತ್ರವು ಬಹುಮತವನ್ನು ಗುರುತಿಸಿದೆ ಎಂದು ಹೇಳಲಾಗುವ ವ್ಯಾಖ್ಯಾನವನ್ನು ಸಡಿಲಗೊಳಿಸಿದರೆ ಬಹುಪಾಲು ಸಮಸ್ಯೆಯನ್ನು ಸಂಪೂರ್ಣವಾಗಿ ಪರಿಹರಿಸಬಹುದು. ನಿರ್ದಿಷ್ಟವಾಗಿ ಹೇಳುವುದಾದರೆ, ರೂಲ್ 184 ಆಟೋಮ್ಯಾಟನ್ಗೆ, ಆವರ್ತಕ ಗಡಿ ಪರಿಸ್ಥಿತಿಗಳೊಂದಿಗೆ ಸೀಮಿತ ಬ್ರಹ್ಮಾಂಡದ ಮೇಲೆ ಓಡುವಾಗ, ಪ್ರತಿ ಕೋಶವು ಅನಂತವಾಗಿ ಆಗಾಗ್ಗೆ ಎರಡು ಸತತ ಹಂತಗಳವರೆಗೆ ಬಹುಸಂಖ್ಯಾತ ಸ್ಥಿತಿಯಲ್ಲಿರುತ್ತದೆ, ಆದರೆ ಸೀಮಿತವಾಗಿ ಅನೇಕ ಬಾರಿ ಮಾತ್ರ ಎರಡು ಸತತ ಹಂತಗಳವರೆಗೆ ಅಲ್ಪಸಂಖ್ಯಾತ ಸ್ಥಿತಿಯಲ್ಲಿರುತ್ತದೆ. ಪರ್ಯಾಯವಾಗಿ, ಶ್ರೇಣಿಯ ಗಾತ್ರದಲ್ಲಿ ರೇಖೀಯವಾದ ಹಲವಾರು ಹಂತಗಳಿಗೆ ರೂಲ್ 184 ಅನ್ನು ನಡೆಸುವ ಹೈಬ್ರಿಡ್ ಆಟೋಮ್ಯಾಟನ್, ನಂತರ ಬಹುಮತದ ನಿಯಮಕ್ಕೆ (ರೂಲ್ 232) ಬದಲಾಗುತ್ತದೆ, ಇದು ಪ್ರತಿ ಕೋಶವನ್ನು ಬಹುಪಾಲು ಸ್ವತಃ ಮತ್ತು ಅದರ ನೆರೆಹೊರೆಯವರಿಗೆ ಹೊಂದಿಸುತ್ತದೆ, ಎಲ್ಲಾ ಸೊನ್ನೆಗಳ ಅಥವಾ ಅಂತಿಮ ಸ್ಥಿತಿಯಲ್ಲಿರುವ ಎಲ್ಲದರ ಪ್ರಮಾಣಿತ ಗುರುತಿಸುವಿಕೆಯ ಮಾನದಂಡದೊಂದಿಗೆ ಬಹುಪಾಲು ಸಮಸ್ಯೆಯನ್ನು ಪರಿಹರಿಸುತ್ತದೆ. ಆದಾಗ್ಯೂ, ಈ ಯಂತ್ರವು ಸ್ವತಃ ಸೆಲ್ಯುಲಾರ್ ಆಟೋಮ್ಯಾಟನ್ ಅಲ್ಲ. ಇದಲ್ಲದೆ, ಫುಕ್ಸ್ನ ಸಂಯೋಜಿತ ನಿಯಮವು ಶಬ್ದಕ್ಕೆ ಬಹಳ ಸೂಕ್ಷ್ಮವಾಗಿದೆ ಮತ್ತು ಯಾವುದೇ ಮಟ್ಟದ ಶಬ್ದಕ್ಕೆ (ಉದಾಹರಣೆಗೆ, ಪರಿಸರದಿಂದ ಅಥವಾ ಕ್ರಿಯಾತ್ಮಕ ತಪ್ಪುಗಳಿಂದ) ಅಸಂಪೂರ್ಣ ವರ್ಗೀಕರಣವಾದ ಗಾಸ್-ಕುರ್ಡ್ಯುಮೋವ್-ಲೆವಿನ್ ಆಟೋಮ್ಯಾಟನ್ ಅನ್ನು ಮೀರಿಸಲು ಸಾಧ್ಯವಿಲ್ಲ ಎಂದು ತೋರಿಸಲಾಗಿದೆ. ಉಲ್ಲೇಖಗಳು ಸೆಲ್ಯುಲಾರ್ ಆಟೋಮ್ಯಾಟಾ