...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Fuzzy sets and systems >Automata theory based on complete residuated lattice-valued logic: Turing machines
【24h】

Automata theory based on complete residuated lattice-valued logic: Turing machines

机译：基于完全剩余格值逻辑的自动机理论：图灵机

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

Automata theory based on complete residuated lattice-valued logic, called L-valued finite automata (L- VFAs), has been established by the second author in 2001. In view of the importance of Turing machines, in this paper, we establish a theory of Turing machines based on complete residuated lattice-valued logic, which is a continuation of C-VFAs. First, we give the definition of L-valued nondeterministic Turing machines (L-NTMs), and observe that the multitape L-NTMs have the same language-recognizing power as the single-tape L-NTMs. We give some related properties of L-valued Turing machines, and discuss computing with fuzzy letters via L-valued "Hiring machines. Second, we introduce the concepts of L-valued recursively enumerable languages and L-valued recursive languages, and obtain some equivalent relations. Some results concerning the characterization of n-recursively enumerable sets are given, and the super-computing power of L-valued TUring machines is investigated. We also prove that L-valued deterministic Turing machines and L-NTMs are not equivalent in the sense of recognizing or deciding languages. Finally, we show that there is no universal L-valued Turing machine. However, a universal L-valued Turing machine exists if the membership degrees of L-valued sets are restricted to a finite complete residuated lattice with universal bounds 0 and 1.
机译：第二作者于2001年建立了基于完全剩余格值逻辑的自动机理论，称为L值有限自动机（L-VFA）。鉴于图灵机的重要性，在本文中，我们建立了一个理论图灵机基于完全残差的晶格值逻辑，是C-VFA的延续。首先，我们给出了L值非确定性图灵机（L-NTM）的定义，并观察到多带L-NTM具有与单带L-NTM相同的语言识别能力。我们给出了L值图灵机的一些相关属性，并讨论了通过L值“租用机”使用模糊字母进行的计算。其次，我们介绍了L值递归可枚举语言和L值递归语言的概念，并获得了一些等价的给出了关于n个递归可枚举集的刻画的一些结果，研究了L值TUring机的超级计算能力，还证明了L值确定性图灵机和L-NTM在等价性上不等价。最后，我们证明不存在通用的L值图灵机，但是如果L值集的隶属度被限制为一个有限的完整剩余格，则存在一个通用的L值图灵机。通用界限0和1。

著录项

  • 来源
    《Fuzzy sets and systems》 |2012年第2012期|p.43-66|共24页
  • 作者

    Lihua Wu; Daowen Qiu; Hongyan Xing;

  • 作者单位

    Department of Computer Science, Sun Yat-sen University, Guangzhou 510006, China,SQIG - Instituto de Telecomunicacoes, Departamento de Matemdtica, Instituto Superior Tecnico, Universidade Tecnica de Lisboa, Avenida Rovisco Pais 1049-001, Lisbon, Portugal;

    Department of Computer Science, Sun Yat-sen University, Guangzhou 510006, China,SQIG - Instituto de Telecomunicacoes, Departamento de Matemdtica, Instituto Superior Tecnico, Universidade Tecnica de Lisboa, Avenida Rovisco Pais 1049-001, Lisbon, Portugal,The State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences, Beijing 100080, China;

    Department of Computer Science, Sun Yat-sen University, Guangzhou 510006, China;

  • 收录信息 美国《科学引文索引》(SCI);美国《工程索引》(EI);
  • 原文格式 PDF
  • 正文语种 eng
  • 中图分类
  • 关键词

    non-classical logic; residuated lattices; turing machines; recursively enumerable languages; universal turing machines;

    机译：非经典逻辑剩余格图灵机;递归可枚举的语言;通用图灵机;

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号