آلن تورینگ در 1936 در قضیه تاریخی‌اش محدودیت‌های توان محاسباتی را اثبات کرد. وی ثابت کرد که هیچ راه میان بُر‌وسریع برای پیش‌گویی خروجی یک برنامه دلخواه وجود ندارد. این قضیه مثالی از تقلیل‌ناپذیری محاسباتی است. ولفرام حدود پنج دهه بعد چنین عنوان کرد که تقلیل‌ناپذیری محاسباتی برای بسیاری از سیستم‌های فیزیکی حقیقی برقرار است.

درسال 1948 جان فون نویمان هنگام یافتن مدل ریاضی برای رشد و نمو سلولها، اتوماتای سلولی را ابداع کرد...

‌فهرست