Payamvdn/NorthPersian_fa_wiki huggingface dataset:
عبارتی در صورتی می توانیم بین دو قسمت مختلف حلقه موازی سازی انجام که در گراف وابستگی به هم متصل نباشند. دقت داده ها. ممکن است متغیرهای موجود در بردارها از نوع متفاوتی باشند و ممکن است در انجام عملیات های مجبور باشیم بعضی از آن ها را به هم تبدیل کنیم و برای همین موازی سازی می تواند باعث به وجود آمدن خطا در داده ها شود. وابستگی داده ها. همان طور که در بخش قبل گفتیم اولین مرحله در روش برداری سازی خودکار پیدا کردن وابستگی بین داده هاست. به عبارتی نباید دو دو خط از حلقهٔ مورد نظر که به هم مرتبطند را هم زمان انجام دهیم برای مثال: for (i = 0; i &lt; 128; i++) { a[i] = a[i+1]; a[i] = a[i-1]; }در مثال بالا همان طور که می بینیم اگر دو جملهٔ متوالی را بخواهیم به صورت موازی با هم انجام دهیم به نتیجهٔ غلطی می رسیم. پس بنا بر مثالی که در بالاتر دیدیم وابستگی داده ها اهمیت زیادی دارد و با ساخت درخت وابستگی و انجام الگوریتم های مشخص می توانیم این موازی سازی ها را انجام دهیم. زمان اجرا در مقابل زمان کامپایل. برخی از برداری سازی ها در زمان کامپایل به صورت کامل انجام می گیرند به عبارتی می توان در همان زمان کامپایل وابستگی داده
ها به هم را تشخیص داد و با استفاده از برداری سازی، موازی سازی انجام داد برای مثال در همان زمان کامپایل کد زیر را می توان به صورت کامل بر روی آن انجام داد. int a[128]; int b[128]; // initialize b for (i = 0; i&lt;128; i++) a[i] = b[i] + 5;اما لزوماً همهٔ کدها مانند کد بالا را نمی توان در زمان کامپایل برداری سازی را بر روی آن انجام داد. برخی از کدها ممکن است در زمان اجرا به هم مرتبط شوند پس نمی توان در همان زمان کامپایل گراف وابستگی آن ها را به طور کامل انجام داد. برای مثال کد زیر کاملاً مشابه کد بالاست با این تفاوت که دو متغیر در زمان اجرا ساخته می شوند و در زمان کامپایل قابل تشخیص نیستند. int *a = malloc(128*sizeof(int)); int *b = malloc(128*sizeof(int)); // initialize b for (i = 0; i&lt;128; i++, a++, b++) *a = *b + 5; // ... free(b); free(a); تکنیک ها. دراین جا به یک مثال ساده برای مفهوم شدن نحوهٔ برداری سازی ارائه می کنیم. این مثال را در نظر بگیرید: for (i = 0; i &lt; 1024; i++) C[i] = A[i]*B[i]; بر اساس میزان موازی سازی که می توانیم انجام دهیم برداری سازی انجام می شود. مثلاً اینجا می خواهیم هر سه جمله را
به طور موازی با هم ضرب کنیم. for (i = 0; i &lt; 1024; i+=4) C[i:i+3] = A[i:i+3]*B[i:i+3];
ورویر مارتیروسی پانویان (؛ ؛ زاده – درگذشته ) یک بازیگر اهل ارمنستان بود. وی بین سال های ۱۹۶۷ تا ۱۹۷۷ میلادی فعالیت می کرد. زندگی نامه. وی در ۳ سپتامبر ۱۹۰۷ در وانادزور، استان لوری به دنیا آمد وی همچنین برندهٔ جوایزی همچون هنرمند مردمی ارمنستان شوروی (۱۹۶۱) شده است. وی در ۲۷ مهٔ ۱۹۷۷ در سن ۶۹ سالگی در آرتاشات درگذشت. گزیده فیلمشناسی. از فیلم ها یا برنامه های تلویزیونی که وی در آن نقش داشته است می توان به ناهاپتاشاره کرد.
آرتاشس مکرتچی گیوداکیان (؛ ؛ – ) یک بازیگر اهل ارمنستان بود. وی بین سال های ۱۹۷۴ تا ۱۹۹۲ میلادی فعالیت می کرد. زندگی نامه. وی برندهٔ جوایزی همچون هنرمند شایسته ارمنستان شوروی شده است. گزیده فیلمشناسی. از فیلم ها یا برنامه های تلویزیونی که وی در آن نقش داشته است می توان به "ناهاپت" (۱۹۷۷)، "رفیق پانجونی" (۱۹۹۳)، "ستاره امید" (۱۹۷۸)، "یک تکه از آسمان" (۱۹۸۰)، "آرئویک" (۱۹۷۸)، "تانگوی کودکی ما" (۱۹۸۴) اشاره کرد.
ماراته آ (به ایتالیایی: Maratea) یک کومونه در ایتالیا است که در استان پوتنزا واقع شده است. ماراته آ ۶۷ کیلومتر مربع مساحت و ۵٬۲۰۵ نفر جمعیت دارد و ۳۰۰ متر بالاتر از سطح دریا واقع شده است. خواهرخوانده. شهرهای بولتسانو، سنتو، فرارا، کاروزینو و آوترانا خواهرخوانده های ماراته آ هستند.
در علوم نظری کامپیوتر، الگوریتم مارکوف یک سیستم بازنویسی رشته ای است که قوانین گرامر-مانندی را بر روی رشته ای از نمادها اعمال می کند. الگوریتم مارکوف به عنوان یک تورینگ کامل نشان داده شده است که به این معنی است که آن ها به عنوان یک مدل کلی از یک سری محاسبات مناسب هستند که می توانند بیانگر هر عبارت ریاضی از علامت ساده خود باشد. الگوریتم مارکوف به نام آندرس مارکوف ریاضیدان سابق نامگذاری شده است. Refal یک زبان برنامه نویسی مبتنی بر الگوریتم مارکوف است. توصیف. الگوریتم های عادی، کلامی هستند که به عنوان کلماتی که در الفباهای مختلف به کار برده می شوند، در نظر گرفته می شود. تعریف هر الگوریتم عادی شامل دو بخش است: یکی تعریف الفبای الگوریتم (الگوریتم برای کلمات این نمادهای الفبایی به کار برده خواهد شد) و دیگری تعریف برای طرح آن است. طرح الگوریتم عادی یک مجموعه محدود از فرمول هایی است که به اصطلاح به آن ها فرمول جایگزینی می گوییم که هر کدام می تواند ساده یا نهایی باشد. یک فرمول جایگزینی ساده کلماتی هستند به شکل formula_1، که formula_2 و formula_3 دو کلمه دلخواه در الفبای الگوریتم هستند (که به ترتیب سمت چپ و سمت راست در
فرمول جایگزینی نامیده می شوند) به طور مشابه فرمول جایگزینی نهایی کلماتی هستند به شکل formula_4، هستند که formula_2 و formula_3 دو کلمه دلخواه در الفبای الگوریتم هستند. با این فرض که کاراکترهای کمکی formula_7و formula_8 ، به الفبای الگوریتم تعلق ندارند. یک مثال از طرح الگوریتم عادی که شامل الفبای پنج حرفی formula_9 است می تواند مانند طرح زیر باشد. formula_10 روند استفاده از الگوریتم عادی برای یک کلمه دلخواه formula_11 در الفبای الگوریتم، یک توالی گسسته از مراحل ساده است که شامل موارد زیر است. فرض کنیم formula_12 کلمه ای است که در مرحله قبلی الگوریتم به دست آمده است، (یا کلمه اصلی formula_11، اگر مرحله فعلی قدم اول شماست). اگر در بین فرمول های جایگزینی، سمت چپی وجود نداشته باشد که شاملformula_12 باشد، کار الگوریتم تکمیل شده و نتیجه این الگوریتم کلمه formula_12 در نظر گرفته می شود. در غیر این صورت گزینه هایی هستند که در سمت چپ آن ها قسمتی از formula_12 ظاهر شده است اولین گزینه را انتخاب می کنیم، اگر فرمول جایگزینی یه شکل formula_1 باشد پس از بین تمام حالت های مختلفی که می توان formula_12 را به شکل formula_19 نش
ان داد حالتی را انتخاب می کنیم که formula_20 کوچکترین طول را داشته باشد، بعد از اعمال آن قانون نتیجه مرحله فعلی formula_21 می شود و به سراغ مرحله بعد می رویم. حال اگر این فرمول جایگزینی به شکل formula_4 باشد، پس از انجام مراحل قبل که جواب آن به formula_21 ختم می شود و کار الگوریتم به پایان می رسد. برای مثال در طول فرایند به کارگیری الگوریتم با استفاده از طرح بالا، روی کلمه formula_24 به ترتیب کلمات formula_25، formula_26، formula_27، formula_28، formula_29، formula_30، formula_31، formula_32، formula_33، formula_34 و formula_35 ظاهر می شود، پس از آن الگوریتم با نتیجه formula_36 متوقف می شود. هر الگوریتم عادی معادل ماشین تورینگ است و بالعکس، هر ماشین تورینگ معادل الگوریتم عادی است. یک نسخه از تز چرچ-تورینگ که در رابطه با الگوریتم عادی فرموله شده است، اصل نرمالیزاسیون نامیده می شود. الگوریتم های عادی ثابت کرده اند که ابزار مناسبی برای ساخت بسیاری از بخش های برساخت گرایی ریاضیات هستند. علاوه بر این، به طور ذاتی الگوریتم های عادی در تعدادی از ایده های مربوط به اداره اطلاعات نمادها در زبان های برنامه نویسی استفاده
شده است. به عنوان مثال در Refal الگوریتم. قوانین توالی به صورت جفت رشته ها هستند. معمولاً به شکل الگوی → نشان داده می شوند. هر قاعده ممکن است عادی یا نهایی باشد. با توجه به یک رشته ورودی: مثال. مثال زیر نشانگر عملیاتی ساده از الگوریتم مارکوف است. رشته نماد. "I bought a B of As from T S." اجرا. اگر الگوریتم برای مثال بالا به کار برده شود، رشته نماد به روش زیر تغییر خواهد کرد. سپس الگوریتم خاتمه خواهد یافت. مثال دیگر. این قوانین مثالی جالب تر را ارائه می دهد، آن ها اعداد دودویی را به شکل تعداد معادلی خط بازنویسی می کنند. به عنوان مثال ۱۰۱ به یک رشته از ۵ خط متوالی بازنویسی خواهد شد. رشته نماد. "۱۰۱" اجرا. اگر الگوریتم برای مثال بالا اجرا شود. بعد از مراحل زیر الگوریتم متوقف خواهد شد.
سان بازیله (به ایتالیایی: San Basile) یک کومونه در ایتالیا است که در استان کزنتزا واقع شده است. سان بازیله ۱۸ کیلومتر مربع مساحت و ۱٬۲۸۳ نفر جمعیت دارد و ۵۴۰ متر بالاتر از سطح دریا واقع شده است.
کانا (به ایتالیایی: Canna) یک کومونه در ایتالیا است که در استان کزنتزا واقع شده است. کانا ۲۰ کیلومتر مربع مساحت و ۸۲۸ نفر جمعیت دارد و ۴۱۷ متر بالاتر از سطح دریا واقع شده است.
چیکالا (به ایتالیایی: Cicala) یک کومونه در ایتالیا است که در استان کاتانزارو واقع شده است. چیکالا ۹ کیلومتر مربع مساحت و ۹۶۴ نفر جمعیت دارد و ۸۳۷ متر بالاتر از سطح دریا واقع شده است.
کاسانا آلیونیو (به ایتالیایی: Cassano all'Ionio) یک کومونه در ایتالیا است که در استان کزنتزا واقع شده است. کاسانا آلیونیو ۱۵۴ کیلومتر مربع مساحت و ۱۸٬۶۵۲ نفر جمعیت دارد و ۲۵۰ متر بالاتر از سطح دریا واقع شده است.
چینش باد یا برش باد () که گاهی به آن شیب باد نیز گفته می شود، به معنای تغییر سمت و سرعت باد در فاصله نسبتاً کوتاهی در اتمسفر زمین است. به عبارتی دیگر، تغییر محلی بُردار باد یا هریک از مؤلفه های آن در یک راستای معین را چینش باد می گویند. چینش باد به تغییر ناگهانی سرعت باد در یک فاصلهٔ کوتاه افقی گفته می شود که در این شرایط تغییر سریعی در میزان لیفت و در پی آن ارتفاع هواپیما رخ می دهد. همواره میزان زیادی چینش باد در جو موجود است اما برش های باد قوی موجب تشکیل چرخند و تگرگ می شود. همواره میزان زیادی چینش باد در نزدیک جبهه های هوا و رودبادها وجود دارد. چینش باد یک لایه جوی ناپایدار است که در CAT هم به وجود می آید. چینش قائم باد در محیط اطراف چرخندهای حاره ای بسیار با اهمیت است. منظور از چینش باد میزان تغییر در سرعت و جهت باد با افزایش ارتفاع است. هنگامی که برش باد ضعیف باشد توفان که قسمتی از چرخند است به صورت قائم رشد می کند و گرمای نهان ناشی از چگالش در هوایی که مستقیماً در بالای توفان قرار دارد آزاد می شود و به توسعه توفان کمک می کند هنگامی که برش باد قوی تری وجود داشته باشد توفان به صورت اریب و کج در می آید و
گرمای نهان بر روی منطقه گسترده تری آزاد می شود. تعریف. چینش باد به تغییر سرعت برداری باد در فواصل افقی یا عمودی اشاره دارد. خلبانان هواپیما معمولاً چینش باد قابل توجه را تغییر افقی در سرعت برای هواپیماهای سبک و برای هواپیماهای مسافربری در ارتفاع بالا تعریف می کنند. تغییرات سرعت عمودی بیشتر از نیز به عنوان چینش باد قابل توجه برای هواپیما شناخته می شود. چینش باد در سطح پایین می تواند بر سرعت هواپیما در هنگام برخاستن و فرود به روش های فاجعه بار تأثیر بگذارد و خلبانان هواپیما آموزش دیده اند تا از ریزش باد ناشی از ریزپکش (کاهش باد مخالف بیش از ) جلوگیری کنند. چینش باد همچنین یک عامل کلیدی در شکل گیری توفان های تندری شدید است. خطر مضاعف آشفتگی در پرواز نیز اغلب با چینش باد همراه و مرتبط است. دلایل آن شامل موارد زیر است: ویژگی ها. چینش باد اتمسفری معمولاً به عنوان برش عمودی یا افقی باد توصیف می شود. چینش عمودی باد، تغییر در سرعت یا جهت باد با تغییر ارتفاع است. چینش افقی باد، تغییر در سرعت باد با تغییر موقعیت جانبی برای یک ارتفاع معین است. چینش باد یک پدیده هواشناسی ریزمقیاس است که در فاصله بسیار کمی رخ می دهد، اما م
ی توان آن را با پدیده های هواشناسی میان مقیاس یا مقیاس سینوپتیک مانند خط های تندوَزه یا جبهه های هوای سرد مرتبط کرد. چینش باد معمولاً در نزدیکی مراکز ریزپکش و فروپکش ناشی از جبهه های توفان تندری، مناطقی با بادهای سطح پایین محلی بالاتر که به آنها رودبادهای سطح پایین گفته می شود، در نزدیکی کوه ها، وارونگی تابشی که به دلیل آسمان صاف و بادهای آرام رخ می دهد، ساختمان ها، توربین های بادی و قایق های بادبانی دیده می شود. برش باد اثرات قابل توجهی در کنترل هواپیما دارد و تنها یا یکی از دلایل بسیاری از سوانح هوایی بوده است. حرکت صوت در اتمسفر تحت تأثیر چینش باد قرار می گیرد، که می تواند جبهه موج را خم کند و باعث شود صداها در جایی قایل شنیدن باشند که معمولاً شنیده نمی شوند. چینش باد عمودی قوی در تروپوسفر همچنین گسترش چرخند حاره ای را مهار می کند، اما به سازماندهی توفان های تندری جداگانه در چرخه های زندگی طولانی تر کمک می کند که سپس می تواند هوای شدید ایجاد کند. مفهوم گرماباد توضیح می دهد که چگونه تفاوت سرعت باد در ارتفاعات مختلف به تفاوت دمای افقی بستگی دارد و وجود رودباد را توضیح می دهد.
ملیکوکا (به ایتالیایی: Melicuccà) یک کومونه در ایتالیا است که در استان رجو کالابریا واقع شده است. ملیکوکا ۱۷٫۲ کیلومتر مربع مساحت و ۱٬۰۲۸ نفر جمعیت دارد.
چنتولا (به ایتالیایی: Centola) یک کومونه در ایتالیا است که در استان سالرنو واقع شده است. چنتولا ۴۷ کیلومتر مربع مساحت و ۵٬۰۷۳ نفر جمعیت دارد و ۳۳۶ متر بالاتر از سطح دریا واقع شده است.
چروینو (به ایتالیایی: Cervino) یک کومونه در ایتالیا است که در استان کسرتا واقع شده است. چروینو ۸٫۰ کیلومتر مربع مساحت و ۵٬۱۳۷ نفر جمعیت دارد.
ساککو (به ایتالیایی: Sacco) یک کومونه در ایتالیا است که در استان سالرنو واقع شده است. ساککو ۲۳ کیلومتر مربع مساحت و ۵۸۲ نفر جمعیت دارد و ۵۰۰ متر بالاتر از سطح دریا واقع شده است.
اُرریا (به ایتالیایی: Orria) یک کومونه در ایتالیا است که در استان سالرنو واقع شده است. ارریا ۲۶٫۵۵ کیلومتر مربع مساحت و ۱٬۱۶۱ نفر جمعیت دارد و ۵۴۰ متر بالاتر از سطح دریا واقع شده است.
کُنتورسی تِرمه (به ایتالیایی: Contursi Terme) یک کومونه در ایتالیا است که در استان سالرنو واقع شده است. کنتورسی ترمه ۲۸٫۹۰ کیلومتر مربع مساحت و ۳٬۲۸۱ نفر جمعیت دارد و ۲۵۰ متر بالاتر از سطح دریا واقع شده است. خواهرخوانده. شهر مورو لوکانو خواهرخواندهٔ کنتورسی ترمه هست.
چِرازو (به ایتالیایی: Ceraso) یک کومونه در ایتالیا است که در استان سالرنو واقع شده است. چرازو ۴۵٫۹۵ کیلومتر مربع مساحت و ۲٬۵۱۰ نفر جمعیت دارد و ۳۴۰ متر بالاتر از سطح دریا واقع شده است.
در نظریهٔ محاسبات، پیوند دهندهٔ پویا (به انگلیسی: Dynamic Linker) بخشی از سیستم عامل است که وظیفهٔ بارگذاری منابع و کتابخانه های مورد نیاز برنامهٔ اجرایی و پیوند دادن آن ها را به برنامه در زمان اجرا بر عهده دارد. پیوند دادن معمولاً به فرایندی گفته می شود که در آن منابع مورد نیاز یک برنامه قبل از اجرا، در زمان کامپایل و توسط کامپایلر به آن برنامه متصل می شوند تا یک بستهٔ اجرایی (به انگلیسی: Executable) کامل ایجاد شود. در مقابل پیوند دهندهٔ پویا منابع مورد نیاز را در زمان اجرای برنامه در آن بارگذاری کرده و سپس آن ها را به برنامهٔ در حال اجرا مقید (به انگلیسی: Bind) می کند. پیونده دهندهٔ پویا عملیات بارگذاری و پیوند منابع و کتابخوانه ها را در زمان اجرای برنامه بر عهده دارد. به این صورت که کتابخوانه های اشتراکی (به انگلیسی: Shared Libraries) و منابع مورد نیاز برنامه را در زمان اجرا و در صورتی که در حافظهٔ اصلی موجود نباشند، از حافظهٔ پایدار (به انگلیسی: Persistent Storage) به حافظهٔ اصلی منتقل کرده، سپس جدول های پرش (به انگلیسی: Jump Table) برنامهٔ بارگذاری شده را با آدرس های منابع اشتراکی تکمیل و اشاره گرهای (به
انگلیسی: Pointer) با آدرس مطلق برنامه را آدرس دهی می کند. پیاده سازی پیوند دهندهٔ پویا و بارگذار پویا و توانایی ها و کاربردهای آن ها بسته به نوع و ردهٔ سیستم عامل و نوع فایل های اجرایی و منابع مورد نیاز آن ها ممکن است متفاوت باشد. پیاده سازی ها. سیستم های عامل ویندوز. کتابخانهٔ پیوندی پویا (به انگلیسی Dynamic-link library) یا DLL نام پیاده سازی شرکت مایکروسافت از مفهوم کتابخانهٔ اشتراکی است. این پیاده سازی در سیستم های عامل ویندوز و OS/2 به کار گرفته شده است. فایل های کتابخانه ای در این پیاده سازی معمولاً از پسوند DLL استفاده می کنند. ساختار و قالب این فایل ها مانند فایل های اجرایی سیستم عامل ویندوز (فایل های با پسوند EXE) است، از این رو این فایل ها می توانند شامل بخش های مختلفی از جنس کد منبع، اطلاعات برنامه و منابع اجرایی باشند. کتابخانه های اجرایی که تنها شامل اطلاعات و منابع اجرایی باشند را DLLهای منبع می نامند. به عنوان مثالی از این نوع کتابخانه های اشتراکی می توان کتابخانه های آیکون (با پسوند ICL) و برخی از قلم ها (به انگلیسی: font) (با پسوندهای FON و FOT) اشاره کرد. سیستم های عامل بر پایهٔ یونیکس. در
بسیاری از سیستم های عامل بر پایهٔ یونیکس (به انگلیسی: Unix) کتابخانه های اشتراکی کاملاً مانند برنامه های اجرایی عادی هستند. استفاده از این کتابخانه های اجرایی در یک برنامه باعث می شود کتابخانهٔ اشتراکی مورد استفاده قبل از بارگذاری برنامهٔ اصلی در فضای حافظهٔ برنامه قرار گیرد، سپس برنامهٔ اصلی بارگذاری شده، ارجاع های انجام شده در آن به کتابخانه های اشتراکی آدرس دهی می شوند و در نهایت اجرای برنامهٔ اصلی شروع می شود. اگر بنابر علتی بارگذاری کتابخانهٔ اشتراکی موفقیت آمیز نباشد، روال اجرای برنامهٔ اصلی با شکست روبه رو خواهد شد. وظیفهٔ بارگذاری رویه های کتابخانه های اشتراکی و برنامهٔ اصلی در فضای آدرس دهی برنامه و در نهایت شروع روال اجرا بر عهدهٔ پیونددهندهٔ پویا است. در سیستم های عامل لینوکس (به انگلیسی: Linux) فایل های کتابخانه های اجرایی اشتراکی از پسوند SO استفاده می کنند. سیستم های عامل macOS و iOS. در سیستم عامل داروین (به انگلیسی: Darwin) شرکت اپل و سیستم های عامل macOS و iOS که بر پایهٔ آن بنا شده اند نوع پیونده دهندهٔ پویایی که باید برای پیونددادن برنامه و کتابخانه های مورد استفاده اش استفاده شود در زمان پ
یوند مشخص می شود. به این منظور آدرس فایل اجرایی دودویی این پیونددهنده در فضای آدرس دهی پردازه قرار داده می شود. فایل های کتابخانه های اشتراکی در این سیستم های عامل از پسوند DYLIB استفاده می کنند. برنامهٔ اجرایی در این سیستم های عامل می تواند حین اجرای پیوند دهنده یا حین اجرای خود با پیونددهندهٔ پویا تعامل داشته باشد. به این صورت پیوند دهندهٔ پویا منابعی را با برنامه پیوند خواهد داد که در روال اجرای برنامه مورد نیاز هستند. از این رو ممکن است منابع بارگذاری شده در دفعات مختلف اجرای یک برنامه متفاوت باشند. در این سیستم های عامل، یک برنامه می تواند مدت ها پس از شروع اجرایش با تعامل با پیوند دهنده باعث بارگذاری منابع بیشتر یا خارج کردن منابع قبلی از حافظه شود. این رفتار ویژه به منظور ارائهٔ سرویس های مورد نیاز در رابط های برنامه نویسی کاربردی (به انگلیسی: Application Programming Interface یا API) شرکت اپل مانند Cocoa و Objective-C در نظر گرفته شده است. پیونددهندهٔ پویای اپل در سیستم عامل macOS یک پیونده دهندهٔ متن باز است که از طریق پروژهٔ متن باز اپل در دسترس عموم قرار دارد. سیستم های عامل یونیکس بر پایهٔ XCOFF.
در سیستم های عامل بر پایهٔ XCOFF مانند AIX شرکت IBM فایل های کتابخانه های اجرایی اشتراکی از پسوند A استفاده می کنند.
در نظریه پیچیدگی محاسباتی اِن اِل (NL) به کلاس پیچیدگی مسائلی از مسائل تصمیم گیری گفته می شود که توسط ماشین تورینگ غیرقطعی و با حافظه لگاریتمی نسبت به اندازه ورودی، قابل حل هستند. NL تعمیمی از مسائل کلاس اِل است که در مسائل کلاس L مسائلی قرار دارند که با پیچیدگی حافظه لگاریتمی نسبت به اندازه ورودی بر روی ماشین تورینگ قطعی قابل حل هستند. کلاس NL به کمک نمادگذاری NPSPACE نیز قابل تعریف است: formula_1 نتایج مهم در نظریه پیچیدگی کلاس مسائل NL را به برخی از کلاس های دیگر مرتبط می کند. این در حالی است که رابطه NL با برخی دیگر از کلاس ها همچنان به عنوان بعضی از مهم ترین مسائل حل نشده در نظریه پیچیدگی مطرح می شوند. یکی از این مسائل بررسی برقراری تساوی بین L و NL یا به طور دقیق تر "آیا formula_2 است؟" می باشد. ماشین تورینگ مورد بررسی در مسائل پیچیدگی فضا. به کمک تعریف اصلی ماشین تورینگ ساده که تنها دارای یک نوار است، مسائل پیچیدگی فضای لگاریتمی قابل بحث نیستند زیرا اندازه خود ورودی به صورت بدیهی از مرتبه formula_3 است و استفاده از حافظه از مرتبه formula_4 بی معنی خواهد بود. به همین دلیل تعریف ماشین تورینگ تغییر پیدا م
ی کند. در این نوع ماشین تورینگ، دو نوار وجود دارد: نوار فقط-خواندنی که روی آن ورودی قرار داده شده است و این نوار یک سر دارد که آزادانه روی آن می تواند حرکت کند ولی خود نوار غیرقابل تغییر است. نوار دوم هم که نوار خواندن-نوشتن است مانند ماشین تورینگ عادی یک سر دارد و قابلیت خواندن و نوشتن را فراهم می کند. با توجه به اینکه بر روی نوار فقط-خواندنی امکان علامت گذاری خانه های آن و به تبع آن تشخیص دو انتهای چپ و راست نوار وجود ندارد، فرض می کنیم که قابلیت تشخیص رسیدن به دو سر نوار برای ماشین تورینگ وجود دارد. حال به کمک این تعریف از ماشین تورینگ، پیچیدگی فضا برابر با تعداد خانه های خوانده شده بر روی نوار خواندن-نوشتن تعریف می شود و در نتیجه با قرار گرفتن ورودی بر روی نوار فقط-خواندنی، در مسائل کلاس حجمی لگاریتمی، مستقل از نوار ورودی، می توان از لگاریتم اندازه ورودی از نوار خواندن-نوشتن استفاده کرد. مسائل اِن اِل-کامل. مبدّل فضای لگاریتمی. یک مبدّل فضای لگاریتمی یک ماشین تورینگ با تعریف اشاره شده در بالا است که در نوار خواندن-نوشتن آن می تواند تنها شامل formula_4 نماد باشد. مبدل فضای لگاریتمی M تابع formula_6 است و ه
نگامی که formula_7 رشته ورودی روی نوار فقط-خواندن باشد، formula_8 رشته باقی مانده بر روی نوار خواندن-نوشتن در پایان است. در این صورت formula_9 یک تابع قابل محاسبه در فضای لگاریتمی است. زبان formula_10 به زبان formula_11 با فضای لگاریتمی قابل کاهش است اگر یک نگاشت قابل کاهش از formula_10 به formula_11 به وسیله یک تابع قابل محاسبه در فضای لگاریتمی مانند formula_9 وجود داشته باشد. نمادگذاری جمله بالا به صورت زیر است: formula_15 تعریف مسائل اِن اِل-کامل. زبان formula_11 یک زبان NL-Complete است اگر مسائل اِن اِل-کامل. مسائل مشهوری مانند اتصال-ST و 2-ارضاپذیری NL-Complete هستند. در مسئله اتصال-ST به عنوان ورودی یک گراف و دو راس S و T داده می شوند و مسئله تصمیم گیری وجود داشتن یک مسیر از S به T است. در مسئله 2-ارضاپذیری هم ارضاپذیر بودن یک عبارت منطقی حاصل AND منطقی بین چند عبارت که خود این عبارات نیز از OR شدن 2 متغیر تشکیل شده اند، سؤال می شود. نمونه ای از عبارات منطقی به شکل زیر است: formula_20 روابط اِن اِل با سایر مجموعه ها. به دلیل وجود الگوریتم چندجمله ای برای حل مسئله 2-ارضاپذیری و با توجه به NL-Complete بود
ن آن، مجموعه P شامل مجموعه NL می شود. این در حالی است که به سوال هایformula_21 یا formula_22 هنوز جوابی داده نشده است. در مورد مقایسه NL و co-NL ثابت شده است که formula_23. این مسئله در سال 1987 به طور مستقل توسط Neil Immerman و Róbert Szelepcsényi ثابت شد که حالت خاصی از قضیه Immerman-Szelepcsényi است که در آن ثابت می شود کلاس های غیرقطعی پیچیدگی فضا تحت عمل مکمل گیری بسته اند. این دو نفر در سال 1995 جایزه Gödel را دریافت کردند. در پیچیدگی مدار NL را می توان در سلسله مراتب NC قرار داد. در Papadimitriou 1994، قضیه 16.1 آمده است: formula_24 همچنین به کمک قضیه ساویچ می توان NL را به پیچیدگی فضای کلاس مسائل قطعی مرتبط کرد. طبق قضیه ساویچ هر الگوریتمی را که به صورت غیرقطعی با حافظه معینی پیاده سازی شده باشد، می توان با حداکثر مربع آن حجم از حافظه به صورت قطعی پیاده سازی کرد. نتیجه این قضیه در مورد کلاس NL به صورت زیر می شود: formula_25 ویژگی های بسته بودن. طبق آن چه که در بالا گفته شد از قضیه Immerman-Szelepcsényi نتیجه می شود که NL تحت عملگر مکمل گیری بسته است. علاوه بر این NL تحت عملگرهای الحاق و ستاره کلین نیز
بسته است.
مسئلهٔ تناظر پست (به انگلیسی: Post correspondence problem) یک مسالهٔ تصمیم ناپذیر بر روی رشته ها است که در سال ۱۹۴۶ میلادی به وسیلهٔ امیل پست معرفی و اثبات شد. با نگاشت این مسئله بر روی مسائل تصمیم ناپذیر دیگر می توانیم تصمیم ناپذیری آن ها را نیز اثبات کنیم (مانند تصمیم ناپذیری ماشین های تورینگ). علاوه بر این که یکی از دلایل اهمیت این مسئله اثبات دیگر مسائل تصمیم ناپذیر به وسیلهٔ آن است، می توان به این موضوع نیز اشاره نمود که درک و اثبات این مسئله بسیار ساده تر از دیگر مسائل تصمیم ناپذیر، مانند مسالهٔ توقف در ماشین تورینگ است. تعریف مسئله. یک "نمونه" از مسئلهٔ تناظر پست را این گونه تعریف می کنیم: هر نمونه از این مسئله شامل دو لیست از رشته هایی است که بر روی الفبای formula_1 تعریف شده اند. فرض کنید این دو لیست formula_2 و formula_3 نام دارند که برای یک مقدار formula_4 این گونه تعریف می شوند: formula_5 formula_6 برای هر formula_7 جفت formula_8 را یک جفت تناظر می گویند. "جواب" مسئلهٔ تناظر پست را نیز این گونه تعریف می کنیم: برای یک نمونه از مسئله "جواب" وجود دارد اگر دنباله ای از اعداد صحیح مانند formula_9، form
ula_10، … و formula_11 وجود داشته باشد که شرط زیر را ارضاء کند: formula_12 پس به طور کلی مسئلهٔ تناظر پست این گونه تعریف می شود: «"آیا برای یک نمونه از مسئلهٔ تناظر پست جوابی وجود دارد یا خیر؟"» مثال. فرض کنید formula_13 و دو لیست formula_2 و formula_3 را این گونه در نظر بگیرید: یک جواب برای این نمونه با formula_16، این گونه است: formula_17؛ زیرا در این صورت: formula_18 formula_19 که این دو شرط formula_20 را ارضاء می کنند. اثبات تصمیم ناپذیری مسئلهٔ تناظر پست. ایدهٔ کلی برای اثبات تصمیم ناپذیری مسئلهٔ تناظر پست این است که آن را بر روی یک مسئلهٔ تصمیم ناپذیر معروف دیگری نگاشت کنیم و بهترین گزینه مسالهٔ توقف است. این نگاشت را این گونه در نظر بگیرید: «یک مسئلهٔ تناظر پست می تواند یک ماشین تورینگ دلخواه را با یک ورودی خاص اجرا کند. مسئلهٔ تناظر پست در صورتی جواب دارد اگر و فقط اگر ماشین تورینگ ورودی اش را قبول و توقف کند.»
ماشین پُست-تورینگ (به انگلیسی: Post-Touring Machine) نام رده ای خاص از توصیف برنامه های محاسباتی است که بر اساس نسخه ای ساده از ماشین تورینگ تعریف می شود. این نسخهٔ ماشین تورینگ با الهام از مدل ریاضی و ماشین ارائه شده توسط امیل پُست (به انگلیسی: Emel Post) برای محاسبات ساخته و توصیف می شود. یک ماشین پُست-تورینگ همانند ماشین تورینگ از حافظه ای دودویی (به انگلیسی: Binary) و از دو طرف نامتناهی برای انجام محاسبات خود استفاده کرده و از یک الفبای دودویی برای ذخیرهٔ داده در این حافظه بهره می برد (هر خانهٔ حافظه می تواند علامت خورده یا بدون علامت باشد). زبان برنامه نویسی این ماشین از اعمالی ابتدایی مانند انتقال به خانهٔ چپ یا راست از یک خانهٔ حافظه و تغییر مقدار ذخیره شده در یک خانهٔ آن پشتیبانی می کند. در شروع عملیات پردازش تعدادی متناهی از خانه های حافظه علامت خورده و بقیه بدون علامت هستند. ماشین از یکی از خانه های حافظه که به عنوان «خانهٔ آغازین» مشخص شده عملیات خود را شروع کرده و در هر لحظه یکی از این پنج عمل را انجام می دهد: علیرغم شباهت توصیف های امیل پُست و آلن تورینگ (به انگلیسی: Alan Touring) از مدل های محاس
باتی شان، این مدل ها مستقل از هم توسعه یافته و هر دو در سال ۱۹۳۶ منتشر شده اند. اصطلاحات «ماشین پُست-تورینگ» و «برنامهٔ پُست-تورینگ» توسط مارتین دیویس (به انگلیسی: Martin Davis) استاد دانشگاه نیویورک مورد استفاده قرار گرفته اند. مدل پُست. امیل پُست در مقاله ای که در سال ۱۹۳۶ به نام "ضابطه بندی فرایند ترکیبیاتی متناهی - ۱" منتشر کرد مدلی بسیار ساده از محاسبات ارائه کرد و حدس زد این مدل "منطقا معدل مدل بازگشتی" است. درستی این فرض بعداً اثبات شد. مدل پُست با مدل ماشین تورینگ در اعمال پایه ای و قوانین اعمال شده بر آن ها تفاوت هایی دارد. مدل پُست از یک فضای یک بعدی ذخیره سازی دودویی (نوار ذخیره سازی) از دو طرف نامتناهی استفاده می کند و از الفبایی دودویی برای ذخیره سازی اطلاعات در هریک از خانه های این حافظه بهره می برد (هر خانهٔ حافظه می تواند علامت خورده یا بی علامت باشد). در شروع عملیات پردازش، تعداد متناهی از خانه های حافظه علامت دار و باقی خانه ها بدون علامت هستند. ماشین از یکی از خانه های حافظه که به عنوان «خانهٔ آغازین» مشخص شده عملیات خود را شروع کرده و در هر لحظه یکی از این پنج عمل را انجام می دهد: پُست در