Simulation of Turing Machine

International Research Journal of Engineering and Technology (IRJET) e-ISSN: 2395-0056

Volume: 10 Issue: 01 | Jan 2023 www.irjet.net p-ISSN: 2395-0072

Simulation of Turing Machine

1,2,3,4 Student, Dept. of Information Technology ,Vishwakarma Institute of Technology ,Maharashtra, India ***

Abstract - A Turing machine is a mathematical model of 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 algorithmsandtheircomputationalcomplexity,aswellasthe development and analysis of various machine learning techniques. Inthispaper, wepresent asimulationofaTuring machine using a software program that allows for the creation, manipulation, and execution of Turing machine programs. We discuss theimplementation of the simulation anddemonstrateitscapabilitiesthroughaseriesofexamples. Finally, we discuss the potential applications and future directions for this simulation, including its use in education, research, andindustry.

Key Words: Turing machine, Automata theory, Python.

1. INTRODUCTION

ATuringmachineisatheoreticaldevicethatisusedto modelthebehaviorofacomputeralgorithm.Itisnamedafter Alan Turing, the mathematician who first described the conceptinhis1936paper,"OnComputableNumbers,withan ApplicationtotheEntscheidungsproblem."

SimulatingaTuringmachineinvolvescreatingavirtual version of the machine that can be run on a computer. This allowsresearcherstostudythebehaviorofthemachineand howitprocessesinput.Itcanalsobeusedtotest different algorithmsandcomparetheirefficiencyandperformance.

Inthisresearchpaper,wewillexploretheuseofsimulation tostudythebehaviorofaTuringmachine.Wewilldescribethe basic principles of a Turing machine andits components, including the tape, head, and state transition function. We willalsodiscussthevarioustechniquesandalgorithmsused tosimulateaTuringmachineandthebenefitsandlimitations ofthisapproach.Finally,wewillpresentsomecasestudies demonstratingtheusefulnessofsimulationinunderstanding the behavior of a Turing machine and its applications in computerscience.

2. LITERATURE REVIEW

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.Inthefollowingyears,manyresearchershaveused simulationtostudythecomplexityandefficiencyofTuring machines, as well as their ability to solve various computationalproblems.

J.N.TsitsiklisandM.Athans[2]usedsimulationtostudythe behavior of Turing machines in at distributed setting and found that their performance was significantly affected by thecommunicationandsynchronizationamongthedifferent machines.

T.H.Cormenetal.[3]usedsimulationtostudythebehavior ofTuringmachinesinthepresenceofnoiseanderrors,and foundthattheirperformancewassignificantlyaffectedbythe probabilityandmagnitudeoftheerrors.

K.S.Trivedietal,[4]usedsimulationtostudythebehaviorof Turing machines with continuous inputs andoutputs, and foundthattheirperformancewassignificantlyaffectedbythe resolutionandaccuracyoftheinputsandoutputs.

ThepaperbyresearchersfromImperialCollegeLondon[5] foundsomecomputationalandthermodynamicconstraints whichwouldbefacedifwearebuildingaUniversalTuring Machine.Amodelwasproposedbythemwhichimplements multipledistinctcomputationsinparallelbutthismakesthe modelcomplicated.

3. METHODOLOGY

For this model, we researched various existing papersand understoodthefunctioningoftheTuringmachineandfound no clearsimulation ofa Turing machine ina programming language.Consideringthiswecame forwardwitha model designedusingpythonwhichsimulatestheTuringmachine andperformssimplebinaryoperationsbyfollowingallthe rulesoftheTuringmachine.Themodelproposedinthepaper uses the features of object oriented programming like inheritance, using all this a complete Turing machine is simulated.

3.1 Proposed System

Togetthe1'scomplimentofabinarynumber,followthese steps:

1. Writedownthebinarynumberyouwanttofindthe1's complimentof.

2. Determine the length of the binary number. For example,ifthebinarynumberis1010,thelengthis4.

3. Createanewstringofzeroswiththesamelengthasthe binarynumber.Forexample,ifthebinarynumberis1010, createanewstringof0000.

International Research Journal of Engineering and Technology (IRJET) e-ISSN: 2395-0056

Volume: 10 Issue: 01 | Jan 2023 www.irjet.net p-ISSN: 2395-0072

4. For each bit in the binary number, write down its oppositevalueinthecorrespondingpositioninthenew string of zeros. If the bit is a 1, write down a 0 in the correspondingposition.Ifthebitisa0,writedowna1in thecorrespondingposition.

5. Add1tothenewstringofzeros.Todothis,startatthe rightmost (least significant) bit I and add 1 to it. Ifthe resultisgreaterthanorequalto2,carrythe1overtothe nextmostsignificantbitandaddittothatbit. Continue thisprocessuntilyoureachthemostsignificantbit.

3.2 Flowchart

Fig-1: Flowcharttofind1’scomplementusingTuring Machine

Factor value:

4. RESULTS AND DISCUSSIONS

Infig2:theclassTuringMachineperformstheoperationof creatingatape,aheadtomoveontapeandthestatesofthe TuringMachine

Fig-2: ClassTuringMachine

Fig 3: shows the conversion of the input string to its 1’s complement by reading the string from the tape and converting1’sto0’sand0’sto1’s.

Fig-3: ActualConversionLogic

Fig4:showstheoutputwhichisgeneratedbythemodel. Hereasimplebinaryoperationoffinding1’scomplement ofthenumberisdone.Theinputbinarystringisconverted toits1’scomplementusingthemechanismoftheTuring Machine

International Research Journal of Engineering and Technology (IRJET) e-ISSN: 2395-0056

Volume: 10 Issue: 01 | Jan 2023 www.irjet.net p-ISSN: 2395-0072

[6] Kuldeep Vayadande, Aditya Bodhankar, Ajinkya Mahajan, Diksha Prasad, Shivani Mahajan, AishwaryaPujariandRiyaDhakalkar,“Classificationof DepressiononsocialmediausingDistantSupervision”, ITMWebConf.Volume50,2022.

Fig-4:Output

5. LIMITATIONS

[1] The model proposed in the paper takes only a binaryinputtodemonstratetheimplementationofthe Turingmachine.

[2] Thismodelperformsonlyasingleoperationonthe giveninputandreturnsone’scomplementasanoutput.

6.CONCLUSION

WeinvestigateexistingmodelsontheTuringmachineand implemented a model using python that successfully simulates the Turing machine. Came concludes that a mechanismoftheTuringmachinecanbeimplementedina programminglanguage.

7.FUTURE SCOPE

[1] Implementing more computation operations intothemodel.

[2] Adding a graphical userinterface wouldmake it moreuser-friendly.

8. REFERENCES

[1]Mohamed Hamada, “Turing Machine and Automata Simulators”, Procedia Computer Science 18(2),May2013,Doi:10.1016/j.procs.2013.05.314

[2]Max Datchet, “Simulation of Turing machines by a regular rewrite rule”, Theoretical Computer Science 103(1992)409-420Elsevier.

[3] F.C.HennieandR.E.Stearns,“Two-Tapesimulationof multitapeTuringmachines”,JournaloftheAssociation for Computing Machinery, Vol. 13, No. 4(October 1966),pp.533-546

[4] B. Jack Copeland, Richard Sylvan, “Beyond the Universal Turing Machine”, Australasian Journal of Philosophy,1999.

[5] RoryA.Brittain,Nick S.Jones, Thomas E.Auldridge, “What would it take to build a thermodynamically reversibleUniversalTuringMachine?Computational andthermodynamicconstraintsinamoleculardesign”, arXiv:2102.03388,2021.

[7] Kuldeep Vayadande, Rahebar Shaikh, Suraj Rothe, Sangam Patil, Tanuj Baware and Sameer Naik,” Blockchain-BasedLandRecordSystem”,ITMWebConf. Volume50,2022.

[8] Kuldeep Vayadande, Kirti Agarwal, Aadesh Kabra, KetanGangwalandAtharvKinage,”Cryptographyusing AutomataTheory”,ITMWebConf.Volume50,2022

[9] Samruddhi Mumbare, Kunal Shivam, Priyanka Lokhande,SamruddhiZaware,VaradDeshpandeand KuldeepVayadande,”SoftwareControllerusingHand Gestures”,ITMWebConf.Volume50,2022

[10]Preetham, H. D., and Kuldeep Baban Vayadande. "OnlineCrimeReportingSystemUsingPythonDjango."

[11]Vayadande,KuldeepB.,etal."SimulationandTesting of Deterministic Finite Automata Machine." International Journal of Computer Sciences and Engineering10.1(2022):13-17.

[12]Vayadande Kuldeep, et al. "Modulo Calculator Using TkinterLibrary."EasyChairPreprint7578(2022).

[13]Vayadande, kuldeep. "Simulating Derivations of Context-FreeGrammar."(2022).

[14]Vayadande, Kuldeep, Ram Mandhana, Kaustubh Paralkar,DhananjayPawal,SiddhantDeshpande,and Vishal Sonkusale. "Pattern Matching in FileSystem." International Journal of Computer Applications 975: 8887.

[15]Vayadande, Kuldeep, Ritesh Pokarne, Mahalakshmi Phaldesai,TanushriBhuruk,TanmayPatil,andPrachi Kumar. "Simulation Of Conway’s Game Of Life Using CellularAutomata."SIMULATION9,no.01(2022).

[16]Gurav, Rohit, Sakshi Suryawanshi, Parth Narkhede, SankalpPatil,Sejal Hukare,andKuldeepVayadande. "Universal Turing machine simulator." International JournalofAdvanceResearch,Ideas,andInnovationsin Technology,ISSN(2022).

[17]Vayadande, Kuldeep B., Parth Sheth, Arvind Shelke, Vaishnavi Patil, Srushti Shevate, and Chinmayee Sawakare. "Simulation and Testing of Deterministic Finite Automata Machine." International Journal of Computer Sciences and Engineering 10, no. 1 (2022):13-17.

© 2022, IRJET | Impact Factor value: 7.529 | ISO 9001:2008 Certified Journal | Page287

International Research Journal of Engineering and Technology (IRJET) e-ISSN: 2395-0056 Volume: 10 Issue: 01 | Jan 2023 www.irjet.net p-ISSN: 2395-0072

[18]Vayadande, Kuldeep, Ram Mandhana, Kaustubh Paralkar,DhananjayPawal,SiddhantDeshpande,and Vishal Sonkusale. "Pattern Matching in File System." International Journal of Computer Applications975:8887.

[19]Vayadande, Kuldeep B., and Surendra Yadav. "A Review paper on Detection of Moving Object in Dynamic Background." International Journal of Computer Sciences and Engineering 6, no. 9 (2018): 877-880.

[20]Vayadande, Kuldeep, Neha Bhavar, Sayee Chauhan, SushrutKulkarni,AbhijitThorat,andYashAnnapure. Spell Checker Model for String Comparison in Automata.No.7375.EasyChair,2022.

[21]Vayadande, Kuldeep, Harshwardhan More, Omkar More,ShubhamMulay,AtharvaPathak,andVishwam Talnikar."PacMan:GameDevelopmentusingPDAand OOP."(2022).

[22]Preetham, H. D., and Kuldeep Baban Vayadande. "OnlineCrimeReportingSystemUsingPythonDjango."

[23]Vayadande, Kuldeep. "Harshwardhan More, Omkar More, Shubham Mulay, Atahrv Pathak, Vishwam Talanikar,“Pac Man: Game Development usingPDA and OOP”." International Research Journal of Engineering and Technology (IRJET), e-ISSN (2022): 2395-0056.

[24]Ingale, Varad, Kuldeep Vayadande, Vivek Verma, Abhishek Yeole, Sahil Zawar, and Zoya Jamadar. "LexicalanalyzerusingDFA."InternationalJournalof Advance Research, Ideas, and Innovations in Technology,www.IJARIIT.com.

[25]Manjramkar,Devang,AdwaitGharpure,AayushGore, Ishan Gujarathi, and Dhananjay Deore. "A Review Paper on Document text search based on nondeterministicautomata."(2022).

[26]Chandra,Arunav,AashayBongulwar,AayushJadhav, Rishikesh Ahire, Amogh Dumbre, Sumaan Ali, Anveshika Kamble, Rohit Arole, Bijin Jiby, and Sukhpreet Bhatti. Survey on Randomly Generating EnglishSentences.No.7655.EasyChair,2022.

2022, IRJET | Impact Factor value: 7.529 | ISO 9001:2008 Certified Journal |