De Bruijn index
கணித தர்க்கத்தில், டி ப்ரூய்ன் குறியீடு என்பது டச்சு கணிதவியலாளர் நிக்கோலாஸ் கோவர்ட் டி ப்ரூய்ன் என்பவரால் கண்டுபிடிக்கப்பட்ட ஒரு கருவியாகும், இது பிணைக்கப்பட்ட மாறிகளுக்கு பெயரிடாமல் லாம்ப்டா கால்குலஸின் சொற்களைக் குறிக்கிறது. இந்த குறியீடுகளைப் பயன்படுத்தி எழுதப்பட்ட சொற்கள் α-மாற்றத்தைப் பொறுத்தவரை மாறாதவை, எனவே α-சமநிலைக்கான சரிபார்ப்பு சொற்பொருள் சமத்துவத்திற்கான சரிபார்ப்பைப் போன்றது. ஒவ்வொரு டி ப்ரூய்ன் குறியீடும் ஒரு இயற்கையான எண், இது ஒரு λ-காலக்கட்டத்தில் ஒரு மாறியின் நிகழ்வைக் குறிக்கிறது, மேலும் அந்த நிகழ்வுக்கும் அதனுடன் தொடர்புடைய பிணைப்புக்கும் இடையிலான வரம்பில் உள்ள பிணைப்புகளின் எண்ணிக்கையைக் குறிக்கிறது. பின்வருபவை சில எடுத்துக்காட்டுகள்ஃ λx என்ற சொல். λy. x, சில நேரங்களில் K காம்பினேட்டர் என்று அழைக்கப்படுகிறது, இது டி ப்ரூயின் குறியீடுகளுடன் λλ2 என எழுதப்படுகிறது. நிகழ்வுக்கான பைண்டர் x என்பது இரண்டாவது λ ஆகும். சொல் λx. λy. λz. டி ப்ரூய்ன் குறியீடுகளுடன் xz (yz) (S ஒருங்கிணைப்பாளர்), λλλ31 (211) ஆகும். சொல் λz. (λy. y (λx. x)) (λx. z x) என்பது λ (λ1 (λ1)) (λ21). பின்வரும் விளக்கப்படத்தைப் பார்க்கவும், அங்கு பிணைப்புகள் வண்ணமயமானவை மற்றும் குறிப்புகள் அம்புகளுடன் காட்டப்பட்டுள்ளன. டி ப்ரூய்ன் குறியீடுகள் பொதுவாக தானியங்கி தேற்றம் புரோவர்ஸ் மற்றும் லாஜிக் நிரலாக்க அமைப்புகள் போன்ற உயர்-வரிசை பகுத்தறிவு அமைப்புகளில் பயன்படுத்தப்படுகின்றன. முறையான வரையறை முறைப்படி, டி ப்ரூய்ன் குறியீடுகளைப் பயன்படுத்தி எழுதப்பட்ட λ-சொற்கள் (M, N,.) பின்வரும் தொடரமைப்பைக் கொண்டுள்ளன (அடைப்புக்குறிகள் சுதந்திரமாக அனுமதிக்கப்படுகின்றன): M, N,:: = n | M N | λ M இதில் n-0 ஐ விட பெரிய இயற்கை எண்கள்-மாறிகள். ஒரு மாறி n குறைந்தபட்சம் n பைண்டர்களின் (λ) வரம்பில் இருந்தால் பிணைக்கப்பட்டுள்ளது; இல்லையெனில் அது இலவசம். ஒரு மாறி n க்கான பிணைப்பு தளம் n வது பைண்டர் ஆகும், இது எல்லைக்குள் உள்ள பைண்டரில் இருந்து தொடங்குகிறது. λ-சொற்களில் மிகவும் பழமையான செயல்பாடு மாற்றீடு ஆகும்ஃ ஒரு சொல்லில் இலவச மாறிகளை மற்ற சொற்களுடன் மாற்றுவது. எடுத்துக்காட்டாக, β-குறைப்பு (λM) N இல், m இல் உள்ள n1, n2,., nk மாறிகளின் நிகழ்வுகளை நாம் கண்டுபிடிக்க வேண்டும், அவை λM இல் உள்ள λ ஆல் பிணைக்கப்பட்டுள்ளன, வெளிப்புற λ-பைண்டரை அகற்றுவதற்கு பொருந்தும் வகையில் M இன் இலவச மாறிகளை குறைத்து, n1, n2,., nk ஐ N உடன் மாற்ற வேண்டும், ஒவ்வொரு முறையும் N இல் நிகழும் இலவச மாறிகளை பொருத்தமாக அதிகரிக்க வேண்டும், λ-பைண்டர்களின் எண்ணிக்கையுடன் பொருந்த, இதன் கீழ் N என்பது ni இல் ஒன்றுக்கு மாற்றாக இருக்கும்போது தொடர்புடைய மாறி நிகழ்கிறது. எடுத்துக்காட்ட, பயன்பாட்டைக் கவனியுங்கள் (λλ42 (λ13)) (λ51) இது வழக்கமான குறியீட்டில் (λx) எழுதப்பட்ட பின்வரும் சொல்லுடன் ஒத்திருக்கலாம். λy. z x (λu. u x)) (λx. x). படி 1 க்குப் பிறகு, λ4· (λ1·) என்ற சொல்லைப் பெறுகிறோம், அங்கு மாற்றீட்டிற்காக நிர்ணயிக்கப்பட்ட மாறிகள் பெட்டிகளால் மாற்றப்படுகின்றன. படி 2 இலவச மாறிகளைக் குறைக்கிறது, இது λ3⁄2 (λ1⁄2) ஐ அளிக்கிறது. இறுதியாக, படி 3 இல், பெட்டிகளை வாதத்துடன் மாற்றுகிறோம், அதாவது λ51; முதல் பெட்டி ஒரு பைண்டரின் கீழ் உள்ளது, எனவே அதை λ61 உடன் மாற்றுகிறோம் (இது 1 ஆல் அதிகரித்த இலவச மாறிகளுடன் λ51 ஆகும்); இரண்டாவது இரண்டு பைண்டர்களின் கீழ் உள்ளது, எனவே அதை λ71 உடன் மாற்றுகிறோம். இறுதி முடிவு λ3 (λ61) (λ1 (λ71)) ஆகும். முறைப்படி, ஒரு மாற்றீடு என்பது M1.M2. என்று எழுதப்பட்ட வரம்பற்ற சொற்களின் பட்டியலாகும், இதில் மி என்பது ith இலவச மாறிக்கு மாற்றாகும். படி 3 இல் அதிகரித்து வரும் செயல்பாடு சில நேரங்களில் ஷிப்ட் என்று அழைக்கப்படுகிறது மற்றும் எழுதப்படுகிறது k அங்கு k என்பது மாறிகளை அதிகரிப்பதற்கான அளவைக் குறிக்கும் ஒரு இயற்கை எண், மேலும் இது வரையறுக்கப்படுகிறது எடுத்துக்காட்டாக, 0 என்பது அடையாள மாற்றீடு, ஒரு சொல்லை மாற்றாமல் விட்டுவிடுகிறது. M1.M2.Mn என்ற சொற்களின் வரையறுக்கப்பட்ட பட்டியல், M1.M2.Mn. (n + 1). (n + 2) என்ற பதிலை சுருக்குகிறது. n ஐ விட பெரிய அனைத்து மாறிகளையும் மாற்றாமல் விட்டுவிடுகிறது. M என்ற சொல்லுக்கு மாற்றாக s ஐப் பயன்படுத்துவது M [s] என்று எழுதப்படுகிறது. s1 மற்றும் s2 ஆகிய இரண்டு மாற்றீடுகளின் கலவை s1s2 என எழுதப்பட்டு (M1.M2) s = M1 [s]. M2 [s]. M [s1s2] = (M [s1]) [s2] என்ற பண்பை திருப்திப்படுத்துகிறது, மேலும் மாற்று பின்வரும் சொற்களில் வரையறுக்கப்படுகிறதுஃ மேலே உள்ள β-குறைப்புக்கான கோடிட்டுக் காட்டப்பட்ட படிகள் இவ்வாறு சுருக்கமாக வெளிப்படுத்தப்படுகின்றனஃ (λM) N → βM [N]. டி ப்ரூய்ன் குறியீடுகளுக்கான மாற்றீடுகள் λ-சொற்களின் நிலையான "பெயரிடப்பட்ட" பிரதிநிதித்துவத்தைப் பயன்படுத்தும் போது, மாறிகள் லேபிள்கள் அல்லது சரங்களாகக் கருதப்படும் போது, விதிமுறைகளில் எந்தவொரு செயல்பாட்டையும் வரையறுக்கும் போது ஒருவர் வெளிப்படையாக α-மாற்றத்தைக் கையாள வேண்டும். நடைமுறையில் இது சிக்கலானது, திறமையற்றது மற்றும் பெரும்பாலும் பிழை ஏற்படக்கூடியது. எனவே இது போன்ற சொற்களின் வெவ்வேறு பிரதிநிதித்துவங்களைத் தேடுவதற்கு இது வழிவகுத்துள்ளது. மறுபுறம், λ-சொற்களின் பெயரிடப்பட்ட பிரதிநிதித்துவம் மிகவும் பரவலானது மற்றும் மற்றவர்களால் உடனடியாக புரிந்து கொள்ள முடியும், ஏனெனில் மாறிகளுக்கு விளக்கமான பெயர்கள் கொடுக்கப்படலாம். எனவே, ஒரு அமைப்பு டி ப்ரூய்ன் குறியீடுகளை உள்நாட்டில் பயன்படுத்தினாலும், அது பெயர்களுடன் ஒரு பயனர் இடைமுகத்தை வழங்கும். டி ப்ரூய்ன் குறியீடுகளைப் பார்ப்பதற்கான ஒரு மாற்று வழி டி ப்ரூய்ன் நிலைகள் ஆகும், இது மேலே இருந்து அல்லாமல் அடுக்கின் அடிப்பகுதியில் இருந்து மாறிகளை குறியிடுகிறது. இது ரீஇண்டெக்ஸ் இலவச மாறிகளின் தேவையை நீக்குகிறது, எடுத்துக்காட்டாக சூழலை பலவீனப்படுத்தும் போது, அதேசமயம் டி ப்ரூய்ன் குறியீடுகள் ரீஇண்டெக்ஸ் பிணைக்கப்பட்ட மாறிகளின் தேவையை நீக்குகின்றன, எடுத்துக்காட்டாக மற்றொரு சூழலில் ஒரு மூடிய வெளிப்பாட்டை மாற்றும் போது. டி ப்ரூயின் குறியீடுகள் α-மாற்றத்தின் சிக்கலைத் தவிர்க்கும் λ-சொற்களின் ஒரே பிரதிநிதித்துவம் அல்ல. பெயரிடப்பட்ட பிரதிநிதித்துவங்களில், பிட்ஸ் மற்றும் கப்பேயின் பெயரளவு நுட்பங்கள் ஒரு அணுகுமுறையாகும், அங்கு ஒரு λ-காலத்தின் பிரதிநிதித்துவம் மாறி வரிசைமாற்றங்களைப் பயன்படுத்தி மீண்டும் எழுதக்கூடிய அனைத்து சொற்களின் சமநிலை வகுப்பாகக் கருதப்படுகிறது. இந்த அணுகுமுறை Isabelle/HOL இன் பெயரளவு தரவுத்தள தொகுப்பால் எடுக்கப்படுகிறது. மற்றொரு பொதுவான மாற்று உயர்-வரிசை பிரதிநிதித்துவங்களுக்கான முறையீடு ஆகும், அங்கு λ-பைண்டர் ஒரு உண்மையான செயல்பாடாக கருதப்படுகிறது. அத்தகைய பிரதிநிதித்துவங்களில், α-சமநிலை, மாற்று போன்ற பிரச்சினைகள் உள்ளன. ஒரு மெட்டா-லாஜிக்கில் அதே செயல்பாடுகளுடன் அடையாளம் காணப்படுகின்றன. ஒரு ஆதார உதவியாளரில் ஒரு விலக்கு அமைப்பின் மெட்டா-கோட்பாட்டு பண்புகளைப் பற்றி நியாயப்படுத்தும் போது, சில நேரங்களில் முதல்-வரிசை பிரதிநிதித்துவங்களுக்கு தன்னை மட்டுப்படுத்திக் கொள்வதும், அனுமானங்களுக்கு பெயரிடவோ அல்லது மறுபெயரிடவோ செய்யும் திறனைக் கொண்டிருப்பது விரும்பத்தக்கது. உள்ளூரில் பெயரற்ற அணுகுமுறை மாறிகளின் கலவையான பிரதிநிதித்துவத்தைப் பயன்படுத்துகிறது-பிணைக்கப்பட்ட மாறிகளுக்கான டி ப்ரூய்ன் குறியீடுகள் மற்றும் இலவச மாறிகளுக்கான பெயர்கள்-இது பொருத்தமானபோது டி ப்ரூய்ன் குறியீட்டு சொற்களின் α-கனோனிக்கல் வடிவத்திலிருந்து பயனடைய முடியும். பாரெண்ட்ரெக்டின் மாறி மரபு என்பது பொதுவாக சான்றுகள் மற்றும் வரையறைகளில் பயன்படுத்தப்படும் ஒரு மரபு ஆகும், அங்குஃ பிணைக்கப்பட்ட மாறிகள் இலவச மாறிகளிலிருந்து வேறுபட்டவை, மேலும் அனைத்து பிணைப்புகளும் ஏற்கனவே வரம்பில் இல்லாத மாறிகளை பிணைக்கின்றன. ஒரு தூண்டல் வரையறையின் பொதுவான சூழலில், மாநாட்டைப் பயன்படுத்தி ஒரு தூண்டல் வரையறையை மாற்றுவதற்குத் தேவையான α-மாற்றத்தைப் பயன்படுத்த முடியாது, ஏனெனில் ஒரு மாறி ஒரு பிணைப்பு நிலை மற்றும் ஒரு அல்லாத பிணைப்பு நிலை ஆகிய இரண்டிலும் தோன்றலாம். ஒவ்வொரு விதியும் பின்வரும் இரண்டு நிபந்தனைகளை பூர்த்தி செய்தால் தூண்டல் கொள்கை உள்ளதுஃ விதி பெயரளவு தர்க்கத்தின் அர்த்தத்தில் சமமாக உள்ளது, அதாவது விதியின் வளாகத்தைக் கருதி மாறிகளை மறுபெயரிடுவதன் மூலம் அதன் செல்லுபடியாகும் தன்மை மாறாது, விதியில் பிணைப்பு நிலைகளில் உள்ள மாறிகள் தனித்துவமானவை மற்றும் முடிவில் சுதந்திரமாக உள்ளன. ஒருங்கிணைந்த தர்க்கம், மாறி பெயர்களை அகற்றுவதற்கான மிக முக்கியமான வழி. குறிப்புகள் லாம்ப்டா கால்குலஸ்