Structure of Decidable Locally Finite Varieties

تعریف دقیق ریاضی از مفهوم شهودی "الگوریتم" در مقاله کورت گودل [1931] در مورد قضایای حسابی غیرقابل تصمیم گیری رسمی، ضمنی بود. در طول دهه 1930، در کار ریاضیدانانی مانند آلونزو چرچ، استیون کلین، بارکلی راسر و آلفرد تارسکی، ایده گودل به مفهوم تابع بازگشتی تبدیل شد. چرچ این تز را مطرح کرد که امروزه به طور کلی پذیرفته شده است، که یک الگوریتم موثر همان روشی است که خروجی آن تابعی بازگشتی از ورودی است (به طور مناسب به عنوان یک عدد صحیح کدگذاری شده است). با این مفاهیم، ​​ثابت شد که بسیاری از نظریه های آشنا غیرقابل تصمیم گیری (یا غیر بازگشتی) -i هستند. ه. ، اینکه یک الگوریتم مؤثر (تابع بازگشتی) وجود ندارد که به فرد اجازه دهد تعیین کند که کدام جملات متعلق به نظریه هستند. از ابتدا مشخص بود که هر نظریه ای با محتوای ریاضی به اندازه کافی غنی باید غیرقابل تصمیم گیری باشد. از سوی دیگر، برخی نظریه ها با محتوای اساسی قابل تصمیم گیری هستند. نمونه‌هایی از این نظریه‌های تصمیم‌پذیر عبارتند از نظریه جبرهای بولی (Tarski [1949])، نظریه گروه‌های آبلی (Szmiele~ [1955])، و نظریه‌های حساب و هندسه ابتدایی (Tarski [1951]" اما تارسکی این نتایج را کشف کرد. حدود سال 1930). تعیین خطوط دقیق تقسیم بندی بین طبقات نظریه های تصمیم پذیر و غیرقابل تصمیم به هدف مهم پژوهش در این زمینه تبدیل شد. جبر به سادگی هر ساختاری (A, h(i E I)} متشکل از یک مجموعه غیرحفره A و سیستمی از عملیات پایانی Ii روی A است.

A mathematically precise definition of the intuitive notion of "algorithm" was implicit in Kurt Godel's [1931] paper on formally undecidable propo­ sitions of arithmetic. During the 1930s, in the work of such mathemati­ cians as Alonzo Church, Stephen Kleene, Barkley Rosser and Alfred Tarski, Godel's idea evolved into the concept of a recursive function. Church pro­ posed the thesis, generally accepted today, that an effective algorithm is the same thing as a procedure whose output is a recursive function of the input (suitably coded as an integer). With these concepts, it became possible to prove that many familiar theories are undecidable (or non-recursive)-i. e. , that there does not exist an effective algorithm (recursive function) which would allow one to determine which sentences belong to the theory. It was clear from the beginning that any theory with a rich enough mathematical content must be undecidable. On the other hand, some theories with a substantial content are decidable. Examples of such decidabLe theories are the theory of Boolean algebras (Tarski [1949]), the theory of Abelian groups (Szmiele~ [1955]), and the theories of elementary arithmetic and geometry (Tarski [1951]' but Tarski discovered these results around 1930). The de­ termination of precise lines of division between the classes of decidable and undecidable theories became an important goal of research in this area. algebra we mean simply any structure (A, h(i E I)} consisting of By an a nonvoid set A and a system of finitary operations Ii over A.