کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4662142 1633516 2009 8 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Post’s Problem for ordinal register machines: An explicit approach
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
پیش نمایش صفحه اول مقاله
Post’s Problem for ordinal register machines: An explicit approach
چکیده انگلیسی

We provide a positive solution for Post’s Problem for ordinal register machines, and also prove that these machines and ordinal Turing machines compute precisely the same partial functions on ordinals. To do so, we construct ordinal register machine programs which compute the necessary functions. In addition, we show that any set of ordinals solving Post’s Problem must be unbounded in the writable ordinals.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 160, Issue 3, September 2009, Pages 302-309