Turing Machines on Cayley Graphs

被引:0
|
作者
da Cunha, Aubrey [1 ]
机构
[1] Univ Michigan, Ann Arbor, MI 48109 USA
来源
LOGIC, LANGUAGE, INFORMATION AND COMPUTATION, WOLLIC 2011 | 2011年 / 6642卷
关键词
RECURSIVELY ENUMERABLE DEGREES; WORD PROBLEMS; UNSOLVABILITY;
D O I
暂无
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
We present a generalization of standard Turing machines based on allowing unusual tapes. We present a set of reasonable constraints on tape geometry and conclude that the proper degree of generality is Cayley graphs. Surprisingly, this generalization does not lead to yet another equivalent formulation of the notion of computable function. Rather, it gives an alternative definition of the recursively enumerable Turing degrees that does not rely on oracles.
引用
收藏
页码:84 / 94
页数:11
相关论文
共 50 条
  • [31] CAYLEY GRAPHS VERSUS ALGEBRAIC GRAPHS
    Pranjali
    Kumar, Amit
    Yadav, Tanuja
    JOURNAL OF THE INDONESIAN MATHEMATICAL SOCIETY, 2021, 27 (02) : 130 - 136
  • [32] EMBEDDING GRAPHS IN CAYLEY-GRAPHS
    GODSIL, CD
    IMRICH, W
    GRAPHS AND COMBINATORICS, 1987, 3 (01) : 39 - 43
  • [33] Which Haar graphs are Cayley graphs?
    Estelyi, Istvan
    Pisanski, Tomaz
    ELECTRONIC JOURNAL OF COMBINATORICS, 2016, 23 (03):
  • [34] A class of Cayley graphs on cubic graphs
    Wang, S.
    Li, X.
    2001, Xi'an Jiatong University (18):
  • [35] ON EXTENDABILITY OF CAYLEY GRAPHS
    Miklavic, Stefko
    Sparl, Primoz
    FILOMAT, 2009, 23 (03) : 93 - 101
  • [36] Roughness in Cayley graphs
    Shahzamanian, M. H.
    Shirmohammadi, M.
    Davvaz, B.
    INFORMATION SCIENCES, 2010, 180 (17) : 3362 - 3372
  • [37] Integral Cayley Graphs
    Guo, W.
    Lytkina, D., V
    Mazurov, V. D.
    Revin, D. O.
    ALGEBRA AND LOGIC, 2019, 58 (04) : 297 - 305
  • [38] Eigenvalues of Cayley Graphs
    Liu, Xiaogang
    Zhou, Sanming
    ELECTRONIC JOURNAL OF COMBINATORICS, 2022, 29 (02):
  • [39] ON THE WALKS ON CAYLEY GRAPHS
    Arezoomand, Majid
    FACTA UNIVERSITATIS-SERIES MATHEMATICS AND INFORMATICS, 2019, 34 (03): : 481 - 490
  • [40] On quantum Cayley graphs
    Wasilewski, Mateusz
    DOCUMENTA MATHEMATICA, 2024, 29 : 1281 - 1317