کوئی الگورتھم کجھ چار بُعدی شکلاں نوں پچھان نہیں سکدا

کجھ سوالاں دی کوئی ترکیب نہیں۔ ایس لئی نہیں کہ اجے کسے نے لبھی نہیں، سگوں ایس لئی کہ ایہہ ثابت ہو چکیا اے کہ کوئی الگورتھم — کوئی قدم بہ قدم طریقہ، بھاویں کِنا وی لما ہووے، کسے وی کمپیوٹر اُتے چلایا جاوے — ہر واری اوہناں دا ٹھیک جواب نہیں دے سکدا۔ University of Texas at Austin دے کیمرون میک اے. گورڈن (Cameron McA. Gordon) نے چار بُعدی شکلاں بارے اجیہے دو سوال ہور جوڑے نیں۔

کیہ ایہہ اوہی شکل اے؟

ریاضی دان ایہناں شکلاں نوں 4-مینیفولڈ (4-manifolds) آکھدے نیں: اجیہیاں تھاواں (spaces) جو نیڑیوں ویکھیاں ہر تھاں عام چار بُعدی تھاں ورگیاں لگدیاں نیں۔ ایہناں نوں کمپیوٹر دے حوالے کرن لئی، پیپر ایہہ فرض کردا اے کہ ایہہ آپس وچ جوڑے پدھرے ٹوٹیاں توں بنیاں نیں («ٹوٹا وار لکیری»، piecewise linear، جاں PL)، تاں جو ہر اک نوں ڈیٹا دی اک محدود لسٹ نال بیان کیتا جا سکے۔ فیر بنیادی سوال ایہہ اے: اجیہیاں دو شکلاں دتیاں ہون، تے کیہ اوہ لگاتار بگاڑ (continuous deformation) دی حد تیکر اکو جیہیاں نیں؟

1958 وچ، اے. اے. مارکوف (A. A. Markov) نے وکھایا کہ ایس سوال دا کوئی الگورتھم نہیں۔ مارکوف دا ثبوت شکل والے مسئلے نوں گروپاں (groups) بارے اک مسئلے وچ بدل دیندا اے: اجیہے گروپ موجود نیں، جو محدود گنتی دے اصولاں نال بیان کیتے جاندے نیں، جیہناں لئی کوئی الگورتھم ایہہ فیصلہ نہیں کر سکدا کہ اوہناں دے عنصراں دا کوئی دتا میل اکائی (identity) دے برابر اے کہ نہیں — «لفظی مسئلہ» (word problem)۔ اجیہے گروپ توں، اجیہیاں شکلاں بنائیاں جا سکدیاں نیں جیہناں نوں کوئی الگورتھم صرف اوس ناممکن مسئلے نوں حل کر کے ای اک دوجے توں وکھ پچھان سکدا اے۔

پُٹھی گنتی: ست تیکر

مارکوف دی دلیل اوکھیائی نوں خاص شکلاں تیکر وی ٹکا دیندی اے۔ S² لوو، اک عام گیند دی سطح، تے حاصل ضرب S² × S² بناؤ، اک چار بُعدی شکل۔ ایہدیاں k نقلاں آپس وچ جوڑو (اک «جڑیا جوڑ»، connected sum، جو #k لکھیا جاندا اے)۔ کجھ k لئی، کوئی الگورتھم ایہہ فیصلہ نہیں کر سکدا کہ کوئی دتی شکل #k(S² × S²) اے کہ نہیں۔ کیہڑا k؟

پیپر پُٹھی گنتی دا کھُرا لبھدا اے۔ ناحل لفظی مسئلے تے 12 اصولاں والے اک گروپ توں، جو بوریسوف (Borisov) نے 1969 وچ لبھیا، 14 نقلاں دا نتیجہ نکلیا۔ گورڈن نے 2022 وچ ایہنوں 12 تیکر لیاندا۔ ایم. ٹینسر (M. Tancer) نے فریڈمین (Freedman) دی چار بُعدی شکلاں دی درجہ بندی راہیں اک نواں رستہ لبھیا، تے ایہہ رستہ «ٹوپولوجیکل» (topological) روپ وچ، جتھے شکلاں دا پدھرے ٹوٹیاں توں بنیا ہونا ضروری نہیں، 9 تیکر لے گیا۔ ایس کم دا اک پہلاں والا روپ 8 تیکر اپڑیا سی۔ فیر کیگل (Kegel)، لی (Li) تے رین (Ren) نے اک کتے نِکا ناحل گروپ بنایا — 3 جنریٹر (generators) تے 9 اصول — جیہدے نال ٹوپولوجیکل روپ وچ 7 تے پدھرے ٹوٹیاں والے روپ وچ 9 تیکر اپڑیا گیا۔

گورڈن نے ٹینسر دے رستے نوں پدھرے ٹوٹیاں توں بنیاں شکلاں لئی وی کم کرن جوگا بنایا اے، تے ایہہ ثابت کیتا اے:

کوئی اجیہا الگورتھم نہیں جو ایہہ فیصلہ کر سکے کہ کوئی دتا 4-مینیفولڈ، ٹوٹے ٹوٹے دے حساب نال، S² × S² دیاں 7 نقلاں دے جڑے جوڑ ورگا اے کہ نہیں۔

ثبوت دا دل اک لغت (dictionary) اے۔ کیگل، لی تے رین دے گروپ دے ہر لفظ w لئی، گورڈن نے اک چار بُعدی شکل بنائی اے۔ جے w اکائی دے برابر اے، تے اصولاں اُتے اجازت والیاں چالاں دی اک لڑی — اینڈریوز-کرٹس چالاں (Andrews-Curtis moves)، جو شکل نوں بدلے بغیر اوہدا بیان نویں سرے لکھدیاں نیں — ایہہ وکھا دیندی اے کہ شکل بالکل S² × S² دیاں ست نقلاں اے۔ جے نہیں، تے شکل وچ اجیہے چکر (loops) ہوندے نیں جو کس کے اک نقطے تیکر نہیں سنگوڑے جا سکدے — جو S² × S² دیاں ست نقلاں وچ کدی نہیں ہوندا — ایس لئی اوہ اوہ ست نقلاں نہیں ہو سکدی۔ ایس لئی جیہڑا الگورتھم #7(S² × S²) نوں پچھان لیندا، اوہ لفظی مسئلہ حل کر دیندا، جو ناممکن اے۔

گنڈھے ہوئے گولے

دوجا سوال گنڈھاں (knots) بارے اے۔ اک عام گنڈھ تِن بُعدی تھاں وچ گنڈھ پا کے بنھیا اک دائرہ اے، تے ایہہ فیصلہ کرنا کہ کیہ کوئی گنڈھ کھولی جا سکدی اے، ممکن اے: ایہدے لئی اک الگورتھم اے، جو ہاکن (Haken) دا اے۔ اک بُعد اُتے، اک دو بُعدی گولا چار بُعدی تھاں دے اندر گنڈھیا جا سکدا اے۔ ہور اُچے بُعداں وچ، پتہ اے کہ ایہدے برابر دے مسئلے دا کوئی الگورتھم نہیں۔ چار بُعدی گولے S⁴ وچ دو بُعدی گولیاں لئی، کسے نوں نہیں پتہ۔

گورڈن نے ثابت کیتا اے کہ #7(S² × S²) دے اندر، ایہہ فیصلہ کرن لئی کوئی الگورتھم نہیں کہ کوئی دو بُعدی گولا — جاں کوئی وی سطح، رُخ پذیر (orientable) ہووے جاں نہ — بنا گنڈھ (unknotted) اے کہ نہیں۔ ایس دوران، پیپر اوس شکل وچ اک اجیہا گولا بناؤندا اے جیہدے دوالے دی تھاں دا گروپ ناحل لفظی مسئلے والا اے، تے، S² × S² دیاں 12 نقلاں وچ، اک اجیہا گولا جیہدے گروپ وچ ہر اوس گروپ دی اک نقل اے جیہنوں کمپیوٹر بیان کر سکدا اے۔

انعام: صفر نقلاں

پیپر نشانہ صاف دسدا اے: نقلاں دی گنتی صفر تیکر لیاؤنی۔ صفر نقلاں دا مطلب اے آپ چار بُعدی گولا S⁴۔ پنج تے ہور بُعداں وچ، کوئی الگورتھم گولے نوں پچھان نہیں سکدا؛ دو تے تِن بُعداں وچ، پچھان سکدا اے۔ چار بُعد اجے کھلے نیں — تے ایہہ سوال وی کہ کیہ S⁴ وچ گنڈھے ہوئے گولے لبھے جا سکدے نیں۔ ہر گھٹائی گئی نقل دوہاں سوالاں نوں نیڑے لے آؤندی اے۔