International Research Journal of Engineering and Technology (IRJET)
e-ISSN: 2395-0056
Volume: 10 Issue: 01 | Jan 2023
p-ISSN: 2395-0072
www.irjet.net
Simulation of Turing Machine Ajinkya Ghusarkar1, Girish Nikam2, Atharva Thokal3, Sourabh Shintre4 1,2,3,4 Student, Dept. of Information Technology ,Vishwakarma Institute of Technology ,Maharashtra, India
---------------------------------------------------------------------***---------------------------------------------------------------------
Abstract - A Turing machine is a mathematical model of
J. N. Tsitsiklis and M. Athans [2] used simulation to study the behavior of Turing machines in at distributed setting and found that their performance was significantly affected by the communication and synchronization among the different machines.
computation that can be used to simulate the logic of any algorithm that can be expressed as a set of rules. The simulation of a Turing machine allows for the study of algorithms and their computational complexity, as well as the development and analysis of various machine learning techniques. In this paper, we present a simulation of a Turing machine using a software program that allows for the creation, manipulation, and execution of Turing machine programs. We discuss the implementation of the simulation and demonstrate its capabilities through a series of examples. Finally, we discuss the potential applications and future directions for this simulation, including its use in education, research, and industry.
T. H. Cormen et al. [3] used simulation to study the behavior of Turing machines in the presence of noise and errors, and found that their performance was significantlyaffected by the probability and magnitude of the errors. K. S. Trivedi et al, [4] used simulation to study thebehavior of Turing machines with continuous inputs and outputs, and found that their performance was significantly affected by the resolution and accuracy of the inputs and outputs.
Key Words: Turing machine, Automata theory, Python.
The paper by researchers from Imperial College London [5] found some computational and thermodynamic constraints which would be faced if we are building a Universal Turing Machine. A model was proposed by them which implements multiple distinct computations inparallel but this makes the model complicated.
1. INTRODUCTION A Turing machine is a theoretical device that is used to model the behavior of a computer algorithm. It is named after Alan Turing, the mathematician who first described the concept in his 1936 paper, "On Computable Numbers,with an Application to the Entscheidungsproblem."
3. METHODOLOGY For this model, we researched various existing papers and understood the functioning of the Turing machineand found no clear simulation of a Turing machine in a programming language. Considering this we came forward with a model designed using python which simulates the Turing machine and performs simple binary operations by following all the rules of the Turing machine. The model proposed in the paper uses the features of object oriented programming like inheritance, using all this a complete Turing machine is simulated.
Simulating a Turing machine involves creating a virtual version of the machine that can be run on a computer. This allows researchers to study the behavior of the machine and how it processes input. It can also be used to test different algorithms and compare their efficiency andperformance. In this research paper, we will explore the use of simulation to study the behavior of a Turing machine. Wewill describe the basic principles of a Turing machine and its components, including the tape, head, and state transition function. We will also discuss the various techniques and algorithms used to simulate a Turing machine and the benefits and limitations of this approach. Finally, we will present some case studies demonstratingthe usefulness of simulation in understanding the behavior of a Turing machine and its applications in computer science.
3.1 Proposed System To get the 1's compliment of a binary number, follow these steps:
1. Write down the binary number you want to find the1's compliment of.
2. LITERATURE REVIEW
2. Determine the length of the binary number. For
B. A. Trakhtenbrot in 1963, [1] has published a research paper to study the behavior of Turing machines under different conditions and to evaluate their computational power. In the following years, many researchers have used simulation to study the complexity and efficiency of Turing machines, as well as their ability to solve various computational problems.
© 2022, IRJET
|
Impact Factor value: 7.529
example, if the binary number is 1010, the length is 4.
3. Create a new string of zeros with the same length asthe binary number. For example, if the binary number is 1010, create a new string of 0000.
|
ISO 9001:2008 Certified Journal
|
Page 285