ਡੇਟਾ ਕੰਪਰੈਸ਼ਨ ਬਾਰੇ ਵਿਰੋਧਾਭਾਸ

ਡੇਟਾ ਕੰਪਰੈਸ਼ਨ ਦੀ ਸਮੱਸਿਆ, ਇਸਦੇ ਸਰਲ ਰੂਪ ਵਿੱਚ, ਸੰਖਿਆਵਾਂ ਅਤੇ ਉਹਨਾਂ ਦੇ ਸੰਕੇਤਾਂ ਨਾਲ ਸਬੰਧਤ ਹੋ ਸਕਦੀ ਹੈ। ਸੰਖਿਆਵਾਂ ਨੂੰ ਸੰਖਿਆਵਾਂ ਦੁਆਰਾ ਦਰਸਾਇਆ ਜਾ ਸਕਦਾ ਹੈ ("ਗਿਆਰਾਂ" ਨੰਬਰ 11 ਲਈ), ਗਣਿਤਿਕ ਸਮੀਕਰਨ ("ਵੀਹਵੇਂ ਵਿੱਚ ਦੋ" 1048576 ਲਈ), ਸਤਰ ਸਮੀਕਰਨ ("ਪੰਜ ਨੌਂ" 99999 ਲਈ), ਸਹੀ ਨਾਮ ("ਜਾਨਵਰ ਦੀ ਗਿਣਤੀ" 666 ਲਈ, "ਟਿਊਰਿੰਗ ਦੀ ਮੌਤ ਦਾ ਸਾਲ" 1954 ਲਈ), ਜਾਂ ਇਸਦੇ ਆਪਹੁਦਰੇ ਸੰਜੋਗ। ਕੋਈ ਵੀ ਅਹੁਦਾ ਢੁਕਵਾਂ ਹੈ ਜਿਸ ਦੁਆਰਾ ਵਾਰਤਾਕਾਰ ਸਪਸ਼ਟ ਤੌਰ 'ਤੇ ਇਹ ਨਿਰਧਾਰਤ ਕਰ ਸਕਦਾ ਹੈ ਕਿ ਅਸੀਂ ਕਿਸ ਨੰਬਰ ਬਾਰੇ ਗੱਲ ਕਰ ਰਹੇ ਹਾਂ. ਸਪੱਸ਼ਟ ਹੈ, ਆਪਣੇ ਵਾਰਤਾਕਾਰ ਨੂੰ ਦੱਸੋ "ਅੱਠ ਦਾ ਕਾਰਕ" ਬਰਾਬਰ ਨੋਟੇਸ਼ਨ ਨਾਲੋਂ ਵਧੇਰੇ ਕੁਸ਼ਲ "ਚਾਲੀ ਹਜ਼ਾਰ ਤਿੰਨ ਸੌ ਵੀਹ". ਇੱਥੇ ਇੱਕ ਤਰਕਪੂਰਨ ਸਵਾਲ ਪੈਦਾ ਹੁੰਦਾ ਹੈ: ਦਿੱਤੇ ਗਏ ਨੰਬਰ ਲਈ ਸਭ ਤੋਂ ਛੋਟਾ ਸੰਕੇਤ ਕੀ ਹੈ?

ਦਾਰਸ਼ਨਿਕ ਬਰਟਰੈਂਡ ਰਸਲ ਨੇ 1908 ਵਿੱਚ ਪ੍ਰਕਾਸ਼ਿਤ ਕੀਤਾ "ਬੇਰੀ ਦਾ ਵਿਰੋਧਾਭਾਸ", ਜੋ ਉਲਟ ਪਾਸੇ ਤੋਂ ਨੰਬਰ ਨੋਟੇਸ਼ਨ ਦੇ ਮੁੱਦੇ ਨੂੰ ਛੂਹਦਾ ਹੈ: ਸਭ ਤੋਂ ਛੋਟੀ ਸੰਖਿਆ ਕਿਹੜੀ ਹੈ ਜਿਸ ਲਈ ਅੱਸੀ ਅੱਖਰਾਂ ਦੀ ਲੋੜ ਨਹੀਂ ਹੈ?
ਅਜਿਹੀ ਸੰਖਿਆ ਮੌਜੂਦ ਹੋਣੀ ਚਾਹੀਦੀ ਹੈ: ਅੱਸੀ ਰੂਸੀ ਅੱਖਰਾਂ ਅਤੇ ਸਪੇਸ ਤੋਂ ਤੁਸੀਂ ਸਿਰਫ 3480 ਅਹੁਦਿਆਂ ਨੂੰ ਬਣਾ ਸਕਦੇ ਹੋ, ਜਿਸਦਾ ਮਤਲਬ ਹੈ ਕਿ ਅੱਸੀ ਅੱਖਰਾਂ ਦੀ ਵਰਤੋਂ ਕਰਕੇ ਤੁਸੀਂ 3480 ਤੋਂ ਵੱਧ ਨੰਬਰ ਨਹੀਂ ਦੇ ਸਕਦੇ ਹੋ। ਇਸਦਾ ਮਤਲਬ ਇਹ ਹੈ ਕਿ ਇਸ ਤਰੀਕੇ ਨਾਲ 3480 ਤੋਂ ਵੱਧ ਇੱਕ ਨਿਸ਼ਚਿਤ ਸੰਖਿਆ ਨਿਰਧਾਰਤ ਕਰਨਾ ਅਸੰਭਵ ਹੈ।

ਇਸ ਦਾ ਮਤਲਬ ਹੈ ਕਿ ਇਹ ਨੰਬਰ ਅਹੁਦਿਆਂ ਨਾਲ ਮੇਲ ਖਾਂਦਾ ਹੋਵੇਗਾ "ਸਭ ਤੋਂ ਛੋਟੀ ਸੰਖਿਆ ਜਿਸ ਲਈ ਅੱਸੀ ਅੱਖਰ ਕਾਫ਼ੀ ਨਹੀਂ ਹਨ", ਜਿਸ ਵਿੱਚ ਸਿਰਫ਼ 78 ਅੱਖਰ ਹਨ! ਇੱਕ ਪਾਸੇ, ਇਹ ਨੰਬਰ ਮੌਜੂਦ ਹੋਣਾ ਚਾਹੀਦਾ ਹੈ; ਦੂਜੇ ਪਾਸੇ, ਜੇਕਰ ਇਹ ਨੰਬਰ ਮੌਜੂਦ ਹੈ, ਤਾਂ ਇਸਦਾ ਅਹੁਦਾ ਇਸ ਨਾਲ ਮੇਲ ਨਹੀਂ ਖਾਂਦਾ। ਵਿਰੋਧਾਭਾਸ!

ਇਸ ਵਿਰੋਧਾਭਾਸ ਨੂੰ ਖਾਰਜ ਕਰਨ ਦਾ ਸਭ ਤੋਂ ਆਸਾਨ ਤਰੀਕਾ ਮੌਖਿਕ ਸੰਕੇਤਾਂ ਦੀ ਗੈਰ-ਰਸਮੀਤਾ ਦਾ ਹਵਾਲਾ ਦੇਣਾ ਹੈ। ਜਿਵੇਂ, ਜੇਕਰ ਨੋਟੇਸ਼ਨ ਵਿੱਚ ਸਮੀਕਰਨਾਂ ਦੇ ਸਿਰਫ਼ ਇੱਕ ਵਿਸ਼ੇਸ਼ ਤੌਰ 'ਤੇ ਪਰਿਭਾਸ਼ਿਤ ਸਮੂਹ ਦੀ ਇਜਾਜ਼ਤ ਦਿੱਤੀ ਗਈ ਸੀ, ਤਾਂ "ਸਭ ਤੋਂ ਛੋਟੀ ਸੰਖਿਆ ਜਿਸ ਲਈ ਅੱਸੀ ਅੱਖਰ ਕਾਫ਼ੀ ਨਹੀਂ ਹਨ" ਇੱਕ ਵੈਧ ਸੰਕੇਤ ਨਹੀਂ ਹੋਵੇਗਾ, ਜਦੋਂ ਕਿ ਵਿਹਾਰਕ ਤੌਰ 'ਤੇ ਉਪਯੋਗੀ ਸੰਕੇਤਾਂ ਜਿਵੇਂ ਕਿ "ਅੱਠ ਦਾ ਕਾਰਕ" ਸਵੀਕਾਰਯੋਗ ਰਹੇਗਾ।

ਕੀ ਸੰਖਿਆਵਾਂ 'ਤੇ ਕਾਰਵਾਈਆਂ ਦੇ ਕ੍ਰਮ (ਐਲਗੋਰਿਦਮ) ਦਾ ਵਰਣਨ ਕਰਨ ਦੇ ਰਸਮੀ ਤਰੀਕੇ ਹਨ? ਹਨ, ਅਤੇ ਬਹੁਤਾਤ ਵਿੱਚ - ਉਹਨਾਂ ਨੂੰ ਪ੍ਰੋਗਰਾਮਿੰਗ ਭਾਸ਼ਾਵਾਂ ਕਿਹਾ ਜਾਂਦਾ ਹੈ। ਮੌਖਿਕ ਸੰਕੇਤਾਂ ਦੀ ਬਜਾਏ, ਅਸੀਂ ਪ੍ਰੋਗਰਾਮਾਂ ਦੀ ਵਰਤੋਂ ਕਰਾਂਗੇ (ਉਦਾਹਰਨ ਲਈ, ਪਾਈਥਨ ਵਿੱਚ) ਜੋ ਲੋੜੀਂਦੇ ਸੰਖਿਆਵਾਂ ਨੂੰ ਪ੍ਰਦਰਸ਼ਿਤ ਕਰਦੇ ਹਨ। ਉਦਾਹਰਨ ਲਈ, ਪੰਜ ਨੌਂ ਲਈ ਪ੍ਰੋਗਰਾਮ ਢੁਕਵਾਂ ਹੈ print("9"*5). ਅਸੀਂ ਦਿੱਤੇ ਗਏ ਨੰਬਰ ਲਈ ਸਭ ਤੋਂ ਛੋਟੇ ਪ੍ਰੋਗਰਾਮ ਵਿੱਚ ਦਿਲਚਸਪੀ ਲੈਂਦੇ ਰਹਾਂਗੇ। ਅਜਿਹੇ ਪ੍ਰੋਗਰਾਮ ਦੀ ਲੰਬਾਈ ਨੂੰ ਕਿਹਾ ਜਾਂਦਾ ਹੈ ਕੋਲਮੋਗੋਰੋਵ ਦੀ ਗੁੰਝਲਤਾ ਨੰਬਰ; ਇਹ ਇੱਕ ਸਿਧਾਂਤਕ ਸੀਮਾ ਹੈ ਜਿਸ ਵਿੱਚ ਇੱਕ ਦਿੱਤੇ ਨੰਬਰ ਨੂੰ ਸੰਕੁਚਿਤ ਕੀਤਾ ਜਾ ਸਕਦਾ ਹੈ।

ਬੇਰੀ ਦੇ ਵਿਰੋਧਾਭਾਸ ਦੀ ਬਜਾਏ, ਅਸੀਂ ਹੁਣ ਇੱਕ ਸਮਾਨ ਵਿਚਾਰ ਕਰ ਸਕਦੇ ਹਾਂ: ਸਭ ਤੋਂ ਛੋਟੀ ਸੰਖਿਆ ਕੀ ਹੈ ਜੋ ਇੱਕ ਕਿਲੋਬਾਈਟ ਪ੍ਰੋਗਰਾਮ ਆਉਟਪੁੱਟ ਲਈ ਕਾਫ਼ੀ ਨਹੀਂ ਹੈ?

ਅਸੀਂ ਪਹਿਲਾਂ ਵਾਂਗ ਹੀ ਤਰਕ ਕਰਾਂਗੇ: ਇੱਥੇ 2561024 ਕਿਲੋਬਾਈਟ ਟੈਕਸਟ ਹਨ, ਜਿਸਦਾ ਮਤਲਬ ਹੈ ਕਿ ਕਿਲੋਬਾਈਟ ਪ੍ਰੋਗਰਾਮਾਂ ਦੁਆਰਾ 2561024 ਤੋਂ ਵੱਧ ਨੰਬਰਾਂ ਨੂੰ ਆਉਟਪੁੱਟ ਨਹੀਂ ਕੀਤਾ ਜਾ ਸਕਦਾ ਹੈ। ਇਸ ਦਾ ਮਤਲਬ ਹੈ ਕਿ 2561024 ਤੋਂ ਵੱਧ ਕੋਈ ਨਿਸ਼ਚਿਤ ਸੰਖਿਆ ਇਸ ਤਰੀਕੇ ਨਾਲ ਪ੍ਰਾਪਤ ਨਹੀਂ ਕੀਤੀ ਜਾ ਸਕਦੀ।

ਪਰ ਆਓ ਪਾਈਥਨ ਵਿੱਚ ਇੱਕ ਪ੍ਰੋਗਰਾਮ ਲਿਖੀਏ ਜੋ ਸਾਰੇ ਸੰਭਵ ਕਿਲੋਬਾਈਟ ਟੈਕਸਟ ਤਿਆਰ ਕਰਦਾ ਹੈ, ਉਹਨਾਂ ਨੂੰ ਐਗਜ਼ੀਕਿਊਸ਼ਨ ਲਈ ਚਲਾਉਂਦਾ ਹੈ, ਅਤੇ ਜੇਕਰ ਉਹ ਇੱਕ ਨੰਬਰ ਆਉਟਪੁੱਟ ਕਰਦਾ ਹੈ, ਤਾਂ ਇਸ ਨੰਬਰ ਨੂੰ ਪਹੁੰਚਯੋਗ ਲੋਕਾਂ ਦੇ ਸ਼ਬਦਕੋਸ਼ ਵਿੱਚ ਜੋੜਦਾ ਹੈ। ਸਾਰੀਆਂ 2561024 ਸੰਭਾਵਨਾਵਾਂ ਦੀ ਜਾਂਚ ਕਰਨ ਤੋਂ ਬਾਅਦ, ਭਾਵੇਂ ਇਹ ਕਿੰਨਾ ਵੀ ਸਮਾਂ ਲਵੇ, ਪ੍ਰੋਗਰਾਮ ਡਿਕਸ਼ਨਰੀ ਵਿੱਚੋਂ ਗਾਇਬ ਸਭ ਤੋਂ ਛੋਟੀ ਸੰਖਿਆ ਲੱਭਦਾ ਹੈ ਅਤੇ ਉਸ ਨੰਬਰ ਨੂੰ ਪ੍ਰਿੰਟ ਕਰਦਾ ਹੈ। ਇਹ ਸਪੱਸ਼ਟ ਜਾਪਦਾ ਹੈ ਕਿ ਅਜਿਹਾ ਪ੍ਰੋਗਰਾਮ ਕੋਡ ਦੇ ਇੱਕ ਕਿਲੋਬਾਈਟ ਵਿੱਚ ਫਿੱਟ ਹੋਵੇਗਾ - ਅਤੇ ਉਹ ਸੰਖਿਆ ਆਊਟਪੁੱਟ ਕਰੇਗਾ ਜੋ ਕਿ ਇੱਕ ਕਿਲੋਬਾਈਟ ਪ੍ਰੋਗਰਾਮ ਦੁਆਰਾ ਆਉਟਪੁੱਟ ਨਹੀਂ ਕੀਤਾ ਜਾ ਸਕਦਾ ਹੈ!

ਹੁਣ ਕੀ ਫੜਨਾ ਹੈ? ਇਸ ਨੂੰ ਹੁਣ ਨੋਟੇਸ਼ਨ ਦੀ ਅਨੌਪਚਾਰਿਕਤਾ ਲਈ ਜ਼ਿੰਮੇਵਾਰ ਨਹੀਂ ਠਹਿਰਾਇਆ ਜਾ ਸਕਦਾ ਹੈ!

ਜੇ ਤੁਸੀਂ ਇਸ ਤੱਥ ਤੋਂ ਉਲਝਣ ਵਿੱਚ ਹੋ ਕਿ ਸਾਡੇ ਪ੍ਰੋਗਰਾਮ ਨੂੰ ਕੰਮ ਕਰਨ ਲਈ ਇੱਕ ਖਗੋਲ-ਵਿਗਿਆਨਕ ਮਾਤਰਾ ਦੀ ਮੈਮੋਰੀ ਦੀ ਲੋੜ ਹੋਵੇਗੀ - 2561024 ਤੱਤਾਂ ਦਾ ਇੱਕ ਸ਼ਬਦਕੋਸ਼ (ਜਾਂ ਬਿੱਟ ਐਰੇ) - ਤਾਂ ਤੁਸੀਂ ਇਸਦੇ ਬਿਨਾਂ ਵੀ ਉਹੀ ਕੰਮ ਕਰ ਸਕਦੇ ਹੋ: ਬਦਲੇ ਵਿੱਚ 2561024 ਨੰਬਰਾਂ ਵਿੱਚੋਂ ਹਰੇਕ ਲਈ , ਸਾਰੇ 2561024 ਸੰਭਾਵਿਤ ਪ੍ਰੋਗਰਾਮਾਂ ਵਿੱਚੋਂ ਲੰਘੋ, ਜਦੋਂ ਤੱਕ ਕੋਈ ਯੋਗ ਨਹੀਂ ਹੁੰਦਾ। ਇਹ ਮਾਇਨੇ ਨਹੀਂ ਰੱਖਦਾ ਕਿ ਅਜਿਹੀ ਖੋਜ ਬਹੁਤ ਲੰਬੇ ਸਮੇਂ ਤੱਕ ਚੱਲੇਗੀ: ਨੰਬਰ ਅਤੇ ਪ੍ਰੋਗਰਾਮ ਤੋਂ (2561024) 2 ਜੋੜਿਆਂ ਤੋਂ ਘੱਟ ਦੀ ਜਾਂਚ ਕਰਨ ਤੋਂ ਬਾਅਦ, ਇਹ ਖਤਮ ਹੋ ਜਾਵੇਗਾ ਅਤੇ ਉਹ ਬਹੁਤ ਪਿਆਰਾ ਨੰਬਰ ਲੱਭ ਜਾਵੇਗਾ।

ਜਾਂ ਕੀ ਇਹ ਖਤਮ ਨਹੀਂ ਹੋਵੇਗਾ? ਦਰਅਸਲ, ਉਨ੍ਹਾਂ ਸਾਰੇ ਪ੍ਰੋਗਰਾਮਾਂ ਵਿਚੋਂ, ਜਿਨ੍ਹਾਂ ਦੀ ਕੋਸ਼ਿਸ਼ ਕੀਤੀ ਜਾਵੇਗੀ, ਉਥੇ ਹੋਵੇਗਾ while True: pass (ਅਤੇ ਇਸਦੇ ਕਾਰਜਸ਼ੀਲ ਐਨਾਲਾਗ) - ਅਤੇ ਮਾਮਲਾ ਅਜਿਹੇ ਪ੍ਰੋਗਰਾਮ ਦੀ ਜਾਂਚ ਤੋਂ ਅੱਗੇ ਨਹੀਂ ਜਾਵੇਗਾ!

ਬੇਰੀ ਦੇ ਵਿਰੋਧਾਭਾਸ ਦੇ ਉਲਟ, ਜਿੱਥੇ ਕੈਚ ਨੋਟੇਸ਼ਨ ਦੀ ਅਨੌਪਚਾਰਿਕਤਾ ਵਿੱਚ ਸੀ, ਦੂਜੇ ਮਾਮਲੇ ਵਿੱਚ ਸਾਡੇ ਕੋਲ ਇੱਕ ਚੰਗੀ ਤਰ੍ਹਾਂ ਭੇਸ ਵਾਲਾ ਸੁਧਾਰ ਹੈ "ਸਮੱਸਿਆਵਾਂ ਨੂੰ ਰੋਕਣਾ". ਤੱਥ ਇਹ ਹੈ ਕਿ ਇੱਕ ਨਿਸ਼ਚਿਤ ਸਮੇਂ ਵਿੱਚ ਇੱਕ ਪ੍ਰੋਗਰਾਮ ਤੋਂ ਇਸਦਾ ਆਉਟਪੁੱਟ ਨਿਰਧਾਰਤ ਕਰਨਾ ਅਸੰਭਵ ਹੈ। ਖਾਸ ਤੌਰ 'ਤੇ, ਕੋਲਮੋਗੋਰੋਵ ਦੀ ਜਟਿਲਤਾ ਅਣਗਿਣਤ: ਇੱਥੇ ਕੋਈ ਐਲਗੋਰਿਦਮ ਨਹੀਂ ਹੈ ਜੋ ਕਿਸੇ ਦਿੱਤੇ ਨੰਬਰ ਲਈ, ਇਸ ਨੰਬਰ ਨੂੰ ਪ੍ਰਿੰਟ ਕਰਨ ਵਾਲੇ ਸਭ ਤੋਂ ਛੋਟੇ ਪ੍ਰੋਗਰਾਮ ਦੀ ਲੰਬਾਈ ਦਾ ਪਤਾ ਲਗਾਉਣ ਦੀ ਇਜਾਜ਼ਤ ਦਿੰਦਾ ਹੈ; ਜਿਸਦਾ ਮਤਲਬ ਹੈ ਕਿ ਬੇਰੀ ਦੀ ਸਮੱਸਿਆ ਦਾ ਕੋਈ ਹੱਲ ਨਹੀਂ ਹੈ - ਦਿੱਤੇ ਗਏ ਨੰਬਰ ਲਈ ਸਭ ਤੋਂ ਛੋਟੇ ਜ਼ੁਬਾਨੀ ਅਹੁਦਿਆਂ ਦੀ ਲੰਬਾਈ ਦਾ ਪਤਾ ਲਗਾਉਣ ਲਈ।

ਸਰੋਤ: www.habr.com