ذَكَرنَا فِي مُقَدِّمَةِ هَذا الجُزءِ أنَّ إثبَاتَ عَدَمِ قَابِلِيَّةِ مَجموعَةٍ مُعَيَّنَةٍ لِلعَدِّ يَعنِي عَدَمَ وجُودِ خَوارزميَّاتٍ تَحسِمُ التَّسَاؤلَاتِ المُتَعَلِّقَةَ بِأَيٍ مِن عَنَاصِرِهَا وذَلكَ لِكَونِ طَريقَتِنَا الخَوارزمِيَّةِ تَحتَاجُ – بِالتَّعريفِ – لِلتَّمييزِ بَينَ المُدخَلَاتِ حَتَّى تَستطيعَ مُعالَجَتَهَا بِأيِّ شَكلٍ مَطلوبٍ وعَدَمُ إمكانِيَّةِ العَدِّ تَعنِي فِي الحَقيقَةِ عَدَمَ القُدرَةِ عَلى التَّمييزِالتَّامِ (بِطَريقَةٍ تَمَاثُلِيَّةٍ 1:1) بَينَ هَذه المُدخَلَات.
سَنَرَى فِي المِثَالِ التَّالِي أنَّ العَكسَ صَحيحٌ أَيضاً بِمَعنَى : إن أمكَنَنَا إثبَاتُ عَدَمِ وجُودِ خَوَارزمٍ لِحَسمِ تَساؤلٍ مَا عَن أفرَادِ مَجموعَةٍ مِنَ الأشياءِ تُحَقِّقُ صِفَةً مَنطِقِيَّةً مُعينَةً فَهذا يَعنِي أنَّ هَذه المَجموعَةَ غَيرُ قَابِلَةٍ لِلعَدّ.
لِتَكُن م=مَجموعةَ الدَّوالِ الرِّياضِيَّةِ النَّاقِصَةِ (أَي غَيرِ المُعَرَّفَةِ لِكُلِّ نِقَاطِ المَجَال).
السُّؤالُ المَطرُوحُ هوَ : هَل يُمكِنُنَا أن نَعرِفَ – لأَيِّ دَالَّةٍ “د” مِن “م” ومُدخَلٍ “خ” لِهَذِه الدَّالَّةِ – إن كَانَتْ د(خ) لَهَا قِيمَةٌ أَم لَا ؟
فِيمَا يَلي سَنَستَخدِمُ نَموذَجاً مُختَلِفاً لِطَريقَةِ القُطرِ لَكِنَّنَا سَنَتَّفِقُ أَوَّلاً عَلى تَبسيطٍ مُهِمٍّ يُسَهِّلُ عَلينَا إنشاءَ التَّعَابيرِ المَنطقِيَّةِ ذَاتِ المَرجِعِيَّةِ الذَّاتِيَّةِ: سَنَقومُ بِتَرقِيمِ المَقولَاتِ المَنطِقِيَّةِ جَميعِهَا بَأَيَّةِ طَريقَةٍ نَرَاهَا مُناسِبَة. يُمكِنُ لِهَذه الطَّريقةِ أَن تَكونَ شَبيهَةً بِمَا يَفعَلُهُ أَيُّ نِظامِ تَشغِيلٍ حَديثٍ مَثَلاً حِينَمَا يُحَوِّلُ كُلَّ الجُمَلِ الَّتِي يُدخِلُهَا المُستخدِمونَ إلَى النِّظامِ الثُّنائِيِّ عَن طَريقِ نِظامِ الأَسكِي المَعرُوف.
عَادةً مَا يُسَمَّى هَذا التَّرقِيمُ : تَكويدَ جودل عَلى اعتِبَارِ أَنَّهُ أَوَّلُ مَن استَخدَمَهُ بِشَكلٍ مَنهَجِيّ (سَنَرى فِي المَقطَعِ القَادِمِ تَعريفاً دَقيقاً لَه).
إذَا فَعَلنَا هَذا أَمكَنَنَا أَن نَعتَبِرَ كُلّاً مِنَ الدَّوالِ ومُدخَلَاتِهَا أرقَاماً يُمكِنُ لِأيَّةِ دَالَّةٍ نَوَدُّ إنشَاءَهَا استِخدَامَهَا مُبِاشَرَة.
بِالعَودَةِ إلَى السُّؤالِ المَطروحِ : يُظهِرُ البُرهانُ التَّالِي – بِطَريقَةِ القُطرِ – عَدَمَ وجودِ دَالَّةٍ يًمكِنُهَا حَسمَ إن كَانَتْ د(خ) مُعَرَّفَةً أَم لَا لِأيَّةِ دَالَّةٍ “د” ومُدخَلٍ “خ”:
لِنَفتَرِضْ أَنَّهُ تُوجَدُ مِثلُ هَذِهِ الدَّالَّةِ د(#س,#ص) حَيثُ “#س” هُو رَقَمُ دَالَّةٍ مُعَيَّنَةٍ و”#ص” رَقَمُ المُدخَلاتِ المُرادِ مَعرِفَةُ حَالَةِ “س” عِندَها.
عِندَمَا تَكونُ “س” مُتَعَدِّدَةَ المُدخَلَاتِ سَنَصطَلِحُ عَلى كِتَابَةِ هَذهِ المُدخَلاتِ عَلى شَكلِ قَائِمَةٍ: <#ص1,#ص2,…>.
“د” تُحَاكِي “س” بِمَعنَى أنَّه :
– تَكونُ د مُعَرَّفَةً إن كَانَتْ س(#ص) مُعَرَّفَةً وَغَيرَ مُعَرَّفَةٍ فِي الحَالةِ العَكسيَّة –
نَستَطيعُ عِندَ ذَلكَ تَعريفَ دَالَّةٍ أُخرَى مُعَاكِسَةٍ لِلدَّالَةِ “د” (لِنُسَمِّهَا “د~”) كالتَّالِي :
– لِكُلِّ دَالَّةٍ “ح” ومُدخَلَاتٍ “خ”: د~(#ح,#خ) مُعَرَّفَةٌ إذَا كَانَتْ د(#ح,#خ) غَيرَ مُعَرَّفَةٍ ود~(#ح,#خ) غَيرُ مُعرفَةٍ حِينَمَا تَكونُ د(#ح,#خ) مُعَرَّفَة –
لِيكُنْ “#ق” هو رَقَمَ “د~” حَسبَ تَكويدِ جودل.
مَاهِيَ قِيمةُ : د(#ق,<#ق,#خ>) ؟
(أي أَنَّ “د” تُحاكِي “د~” بِتَطبيقِها عَلَى نَفسِها وَعَلى “خ”)
إذَا كَانَت د(#ق,<#ق,#خ>) مُعَرَّفَةً فَهذا يَعنِي: ق(#ق,#خ) مُعَرَّفَةٌ أَي أنَّ د~(#ق,#خ) يَجِبُ أَن تَكونَ مُعَرَّفَة.
لَكِنَّ هَذا مَعناهُ أيضاً أنَّ د(#ق,#خ) غَيرُ مُعَرَّفَةٍ (حَسبَ تَعريفِ “د~”). تَناقُض.
هَذا التَّناقُضُ يَظهِرُ أيضاً فَي حَالَةِ افتراضِ أَن تَكونَ د(#ق,#خ) غَيرَ مُعَرَّفَة.
(نِهايَةُ البُرهَان)
بِهَذا البُرهانِ البَسيطِ – وَالمَنسوبِ فِي الأَصلِ لِتورنج – نَكونُ قَد أثبَتنَا أنَّ مَجموعَةَ الدَّوالِّ النَّاقِصَةِ غَيرُ قَابِلَةٍ لِلعَدّ لِأَنَّهَا إِن لَم تَكُنْ كَذَلِكَ لَكَانَ بِإمكَانِنَا حِسابُ قِيمَةِ كُلِّ تَعابِيرِ الدَّوَالِّ وبِالتَّالِي حِسابُ
د(#ق,<#ق,#خ>)
أَيضاً دُونَ تَنَاقُض.
فِإن تَذَكَّرنَا أَنَّ الدَّوالَ النَّاقِصَةَ مُكافِئةٌ لِمَا أسمَينَاهُ فِي مُقَدِّمَةِ هَذا الجُزءِ “الخَوارزمياتِ” وأنَّ “عَدَمَ التَّعريفِ فِي نُقطَةٍ مَا” مُكافِيءٌ لِعَدَمِ تَوَقُّفِ الخَوارِزمِ عَن العَمَلِ (أَو عَدَمِ إعطَائِهِ مُخرَجاً مُعَيَّناً فِي وَقتٍ مَا) نَكونُ إذاً قَد أثبَتنَا بِهذَا البُرهانِ مَايَلي:
– لَا تُوجَدُ خَوارزميَّاتٍ تَحسِمُ مَسأَلَةَ تَوقُّفِ أَيِّ خَوارزمٍ عِندَ مُدخَلٍ مُعَيَّن.
– مَجموعَةُ الخَوارزمياتِ المُمكِنِ تَطبيقُهَا عَلى الأعدادِ الطَّبيعيةِ غَيرُ قابِلَةٍ لِلعَدّ.
لَن يَشُكَّ القَارئُ المُطَّلِعُ فِي الأَهَمِّيَّةِ العَمَلِيَّةِ لِهاتَينِ المَقولَتَينِ حَيثُ أنَّ مُشكِلَةَ تَوَقُّفِ البَرمجياتِ (الَّتِي هِيَ تَطبيقٌ عَمَلِيٌّ للخوارزميَّاتِ) مِن أَهَمِّ مُشكِلاتِ الصِّنَاعَةِ فِي حَياتِنَا المُعاصِرَة.
