The Turing machine is designed to solve various tasks and verify algorithms for computability. In this paper, the Turing machine is used to compute Boolean functions. The operation of the Turing machine is examined when calculating the unary Boolean function – negation - and sixteen binary Boolean functions. The paper offers programs for the Turing machine and corresponding finite tables for computing Boolean functions. The developed programs are versatile, as computing a specific Boolean function requires only changing four commands in the program. Possible ways to improve the programs are suggested. More compact Turing machine programs for computing binary Boolean functions are presented. The approach can be extended to various fields, including cryptographic systems, logic circuit design, and automated theorem proving, making it a valuable tool for theoretical and practical advancements in information technology. #COMESYSO1120.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Programs for Turing Machine Designed to Compute Boolean Functions and Their Representation as Finite Tables

  • Roman Tsarev,
  • Alexander Pupkov,
  • Pita Jarupunphol,
  • Oleg Ikonnikov,
  • Roman Kuzmich,
  • Maxim Vasilyev,
  • Mareks Parfjonovs

摘要

The Turing machine is designed to solve various tasks and verify algorithms for computability. In this paper, the Turing machine is used to compute Boolean functions. The operation of the Turing machine is examined when calculating the unary Boolean function – negation - and sixteen binary Boolean functions. The paper offers programs for the Turing machine and corresponding finite tables for computing Boolean functions. The developed programs are versatile, as computing a specific Boolean function requires only changing four commands in the program. Possible ways to improve the programs are suggested. More compact Turing machine programs for computing binary Boolean functions are presented. The approach can be extended to various fields, including cryptographic systems, logic circuit design, and automated theorem proving, making it a valuable tool for theoretical and practical advancements in information technology. #COMESYSO1120.