کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
433774 | 689625 | 2015 | 20 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A formalization of multi-tape Turing machines
ترجمه فارسی عنوان
قالب سازی ماشین آلات تورینگ چند نوار
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
ماشین تورینگ، دستگاه جهانی، تأیید خودکار صحت خبره، تئوری تعاملی اثبات، ماتیتا
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
چکیده انگلیسی
We discuss the formalization, in the Matita Theorem Prover, of basic results on multi-tapes Turing machines, up to the existence of a (certified) Universal Machine, and propose it as a natural benchmark for comparing different interactive provers and assessing the state of the art in the mechanization of formal reasoning. The work is meant to be a preliminary step towards the creation of a formal repository in Complexity Theory, and is a small piece in our long-term Reverse Complexity program, aiming to a comfortable, machine independent axiomatization of the field.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Theoretical Computer Science - Volume 603, 25 October 2015, Pages 23–42
Journal: Theoretical Computer Science - Volume 603, 25 October 2015, Pages 23–42
نویسندگان
Andrea Asperti, Wilmer Ricciotti,