Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Về các cấu trúc có thể đếm được bằng thuật toán
Tóm tắt
Đây là một bài viết ngắn dựa trên bài giảng toàn thể được trình bày bởi tác giả tại hội nghị về Tính toán Đại số và Logic tổ chức tại Kazan, từ ngày 1 đến 6 tháng 6 năm 2014. Bài viết giới thiệu một cách tiếp cận mới nhằm đưa hiệu quả vào việc nghiên cứu các cấu trúc đại số. Theo cách tiếp cận này, các đối tượng ban đầu là các miền có dạng ω/E, trong đó E là quan hệ tương đương trên ω. Trong thiết lập này, người ta nghiên cứu các cấu trúc đại số hiệu quả mà các miền có dạng ω/E cho phép. Bài giảng này được khơi dậy từ các bài báo [2, 20, 21], các câu hỏi chưa được giải đáp trong [17], và dựa trên các bài báo [15, 16, 19, 23].
Từ khóa
#cấu trúc đại số #hiệu quả #miền #quan hệ tương đương #tính toánTài liệu tham khảo
K. Ambos-Spies, S. B. Cooper, and S. Lempp, Order 14(2), 101 (1997).
U. Andrews, S. Lempp, J. S. Miller, Keng Meng Ng, Luca San Mauro, and Andrea Sorbi, manuscript, 2012.
W. Baur, Zeitschrift für mathematische Logik und Grundlagen der Mathematik. 20, 37 (1974).
C. Bernardi, Studia Logica 40, 29 (1981).
C. Bernardi and A. Sorbi, The Journal of Symbolic Logic 48(3), 529 (1983).
S. Coskey and J. D. Hamkins, Notre Dame Journal of Formal Logic 52(2), 203 (2011).
S. Coskey, J. D. Hamkins, and R. Miller, http://www.arxiv.org/1109.3375 (2012).
Y. L. Ershov, Algebra and Logic 10(6), 378 (1974).
Y. L. Ershov, Theory of Numberings (Nauka, Moscow, 1977) [In Russian].
E. B. Fokina, Sy-David Friedman, in Proceedings of the Fifth Conference on Computability in Europe (2009), p. 198.
E. B. Fokina, Sy-David Friedman, Mathematical Logic Quarterly 58(1–2), 113 (2012).
E. B. Fokina, Sy-David Friedman, V. S. Harizanov, J. F. Knight, C. F. D. McCoy, and A. Montalbán, The Journal of Symbolic Logic 77(1), 122 (2012).
E. B. Fokina, Sy-David Friedman, and A. Törnquist, Annals of Pure Applied Logic 161(7), 837 (2010).
S. Gao and P. Gerdes, Studia Logica 67(1), 27 (2001).
A. Gavruskin, B. Khoussainov, and F. Stephan, Reducibilities among Equivalence Relations Induced by Recursively Enumerable Structures, submitted.
A. Gavruskin, B. Khoussainov, F. Stephan, and S. Jain, Graphs Realised by r.e. Equivalence Relations, submitted.
S. Goncharov and B. Khoussainov, Contemporary Mathematics 257, 145 (2000).
C. Jockusch, Transactions of the American Mathematical Society 131, 420 (1968).
D. Hirchfeldt and B. Khoussainov, Algebra and Logic 51(5), 652 (2012).
N. Kasymov and B. Khoussainov, Vychislitel’nye Sistemy 116, 3 (1986) [In Russian].
N. Kassimov, Algebra and Logic 31, 21 (1992).
B. Khoussainov, S. Lempp, and T. Slaman, International J. of Algebra and Computation 15(3), 437 (2005).
B. Khoussainov and A. Miasnikov, “On finitely presented expansions of groups”, to appear in Transaction of the AMS (2013).
B. Khoussainov and R. Shore, Ann. Pure Applied Logic 93, 153 (1999).
A. H. Lachlan, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 33, 43 (1987).
A. I. Maltsev, Algebra i Logika 3(4), 5 (1963).
Luca San Mauro, Master’s thesis (University of Siena, 2011).
J. Miller, Proceedings of the American Mathematical Society 140(5), 1617 (2012).
E. Noether, Mathematische Annalen 83, 24 (1921).
P. S. Novikov, Proceedings of the Steklov Institute of Mathematics 44, 1 (1955) [In Russian].
P. Odifreddi, Classical Recursion Theory (North-Holland, 1989).
R. I. Soare, Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets (Springer Verlag, Berlin-New York, 1987).
A. Visser, in To H. B. Curry: Essays on Combinatory Logic, Lambda Calculus and Formalism (Academic, London, 1980), pp. 259–284.