مورچهٔ لنگتون گونه ای خاص از ترمایت ( نوعی ماشین محاسبهٔ تورینگ دو بعدی ) است که در سال ۱۹۸۶ توسط کریس لنگتون ابداع شده است، همچنین می توان مورچهٔ لنگتون را اتوماتون سلولی با همسایگی فون نویمان دانست. این ماشین همانند بسیاری از دیگر نمونه های اتوماتای سلولی مصداقی از یک سیستم پیچیده با قواعد ساده است که بر حسب قواعد می تواند رفتاری پیچیده، تصادفی یا ساده داشته باشد. در سال ۲۰۰۰ با اثبات امکان شبیه سازی هر مدار دیجیتال دلخواه با مورچهٔ لنگتون، ماشین محاسبهٔ تورینگ بودن این ماشین اثبات[ ۱] شد. افراد مختلفی ایدهٔ مورچهٔ لنگتون را در جهات مختلف گسترش داده اند، برای مثال ترمایت ها[ ۲] با الگو گرفتن از مورچهٔ لنگتون ابداع شده اند که خود گونه ای از ماشین محاسبهٔ تورینگ هستند.
مورچهٔ لنگتون از یک صفحهٔ شطرنجی دو بعدی نامتنهاهی تشکیل شده است که یک مورچه بر روی آن در چهار جهت اصلی حرکت می کند. مورچه بر یکی از این خانه های صفحه قرار دارد. در هر نوبت، مورچه با توجه به رنگ خانه ای که بر روی آن قرار دارد رنگ آن خانه را به رنگ دیگری تغییر می دهد و جهت حرکتش را تغییر می دهد و یک خانه حرکت می کند. [ ۳]
در نمونهٔ اولیه هر خانه می تواند یکی از دو رنگ سفید یا سیاه را داشته باشد. مورچه در صورتی که بر خانهٔ سفید قرار داشته باشد ۹۰ درجه به راست می چرخد، رنگ خانه را تغییر می دهد و به خانهٔ بعدی می رود. در صورتی که مورچه بر روی خانهٔ سیاه قرار داشته باشد ۹۰ درجه به چپ می چرخد، رنگ خانه را تغییر می دهد و به خانهٔ بعدی می رود.
می توان با گسترش مجموعهٔ رنگ ها، یا تغییر دادن قاعدهٔ حرکت مورچه نمونه های متعددی از مورچهٔ لنگتون را به دست آورد که هرکدام رفتاری متفاوت با دیگری دارند. در واقع می توان صفحهٔ دو بعدی را مشابه نوار حافظهٔ ماشین تورینگ، محل مورچه را سر ماشین تورینگ و قاعدهٔ حرکت مورچه را قاعدهٔ حرکت سر ماشین تورینگ در نظر گرفت. همچنین می توان مورچهٔ لنگتون را یک ماشین سلولی در نظر گرفت که در آن، صفحهٔ شطرنجی صفحهٔ ماشین است و به ازای n رنگ در مورچهٔ لنگتون در ماشین سلولی ۵n رنگ وجود دارد. هر خانهٔ خالی در صفحهٔ مورچهٔ یکی از n رنگ را دارد و برای خانهٔ مورچه دار، یکی از 4n رنگ دیگر را انتخاب می کنیم که نشان دهندهٔ رنگ خانه در مورچهٔ لنگتون، حضور مورچه در آن و جهت گیری مورچه است. قوانین تغییر ماشین هم همسایگی فون نویمان هر خانه را در نظر می گیرد و آن خانه و همسایگی آن را مشابه قوانین مورچهٔ لنگتون تغییر می دهد.
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفمورچهٔ لنگتون از یک صفحهٔ شطرنجی دو بعدی نامتنهاهی تشکیل شده است که یک مورچه بر روی آن در چهار جهت اصلی حرکت می کند. مورچه بر یکی از این خانه های صفحه قرار دارد. در هر نوبت، مورچه با توجه به رنگ خانه ای که بر روی آن قرار دارد رنگ آن خانه را به رنگ دیگری تغییر می دهد و جهت حرکتش را تغییر می دهد و یک خانه حرکت می کند. [ ۳]
در نمونهٔ اولیه هر خانه می تواند یکی از دو رنگ سفید یا سیاه را داشته باشد. مورچه در صورتی که بر خانهٔ سفید قرار داشته باشد ۹۰ درجه به راست می چرخد، رنگ خانه را تغییر می دهد و به خانهٔ بعدی می رود. در صورتی که مورچه بر روی خانهٔ سیاه قرار داشته باشد ۹۰ درجه به چپ می چرخد، رنگ خانه را تغییر می دهد و به خانهٔ بعدی می رود.
می توان با گسترش مجموعهٔ رنگ ها، یا تغییر دادن قاعدهٔ حرکت مورچه نمونه های متعددی از مورچهٔ لنگتون را به دست آورد که هرکدام رفتاری متفاوت با دیگری دارند. در واقع می توان صفحهٔ دو بعدی را مشابه نوار حافظهٔ ماشین تورینگ، محل مورچه را سر ماشین تورینگ و قاعدهٔ حرکت مورچه را قاعدهٔ حرکت سر ماشین تورینگ در نظر گرفت. همچنین می توان مورچهٔ لنگتون را یک ماشین سلولی در نظر گرفت که در آن، صفحهٔ شطرنجی صفحهٔ ماشین است و به ازای n رنگ در مورچهٔ لنگتون در ماشین سلولی ۵n رنگ وجود دارد. هر خانهٔ خالی در صفحهٔ مورچهٔ یکی از n رنگ را دارد و برای خانهٔ مورچه دار، یکی از 4n رنگ دیگر را انتخاب می کنیم که نشان دهندهٔ رنگ خانه در مورچهٔ لنگتون، حضور مورچه در آن و جهت گیری مورچه است. قوانین تغییر ماشین هم همسایگی فون نویمان هر خانه را در نظر می گیرد و آن خانه و همسایگی آن را مشابه قوانین مورچهٔ لنگتون تغییر می دهد.
wiki: مورچه لنگتون