A simple implementation of a Turing Machine in Java (which I wrote the night before a Theory of Computation exam instead of studying)

MachineLibrary.java

package tm;

public final class MachinesLibrary 
{
	private MachinesLibrary() {}
	
	public static TuringMachine EqualBinaryWords()
	{
		TuringMachine newTM = new TuringMachine();
		newTM.addState("q1");
		newTM.addState("q2");
		newTM.addState("q3");
		newTM.addState("q4");
		newTM.addState("q5");
		newTM.addState("q6");
		newTM.addState("q7");
		newTM.addState("q8");
		newTM.addState("qa");
		newTM.addState("qr");
		newTM.setStartState("q1");
		newTM.setAcceptState("qa");
		newTM.setRejectState("qr");
		newTM.addTransition("q1", '1', "q3", 'x', true);
		newTM.addTransition("q1", '0', "q2", 'x', true);
		newTM.addTransition("q1", '#', "q8", '#', true);
		newTM.addTransition("q2", '0', "q2", '0', true);
		newTM.addTransition("q2", '1', "q2", '1', true);
		newTM.addTransition("q2", '#', "q4", '#', true);
		newTM.addTransition("q3", '0', "q3", '0', true);
		newTM.addTransition("q3", '1', "q3", '1', true);
		newTM.addTransition("q3", '#', "q5", '#', true);
		newTM.addTransition("q4", 'x', "q4", 'x', true);
		newTM.addTransition("q4", '0', "q6", 'x', false);
		newTM.addTransition("q5", 'x', "q5", 'x', true);
		newTM.addTransition("q5", '1', "q6", 'x', false);
		newTM.addTransition("q6", '0', "q6", '0', false);
		newTM.addTransition("q6", '1', "q6", '1', false);
		newTM.addTransition("q6", 'x', "q6", 'x', false);
		newTM.addTransition("q6", '#', "q7", '#', false);
		newTM.addTransition("q7", '0', "q7", '0', false);
		newTM.addTransition("q7", '1', "q7", '1', false);
		newTM.addTransition("q7", 'x', "q1", 'x', true);
		newTM.addTransition("q8", 'x', "q8", 'x', true);
		newTM.addTransition("q8", '_', "qa", '_', true);
		return newTM;		
	}

}

Main.java

package main;

import tm.*;

public class Main 
{

	public static void main(String[] args) 
	{
		TuringMachine TM1 = MachinesLibrary.EqualBinaryWords();
		
		boolean done = TM1.Run("010000110101#010000110101", false);
		if (done==true)
		{
			System.out.println("The input was accepted.");
		}
		else
		{
			System.out.println("The input was rejected.");
		}
	}

}

TuringMachine.java

package tm; 

import java.util.*;



public class TuringMachine 
{
	private Set<String> StateSpace;
	private Set<Transition> TransitionSpace;
	private String StartState;
	private String AcceptState;
	private String RejectState;
	
	private String Tape;
	private String CurrentState;
	private int CurrentSymbol;
		
	class Transition
	{
		String readState;
		char readSymbol;
		String writeState;
		char writeSymbol;
		boolean moveDirection;	//true is right, false is left
		
		boolean isConflicting(String state, char symbol)
		{
			if (state.equals(readState) && symbol == readSymbol)
			{
				return true;
			}
			else
			{
				return false;			
			}
		}		
	}
	
	
	public TuringMachine()
	{
		StateSpace = new HashSet<String>();
		TransitionSpace = new HashSet<Transition>();
		StartState = new String("");
		AcceptState = new String("");
		RejectState = new String("");
		Tape = new String("");
		CurrentState = new String("");
		CurrentSymbol = 0;
		
	}
	
	public boolean Run(String input, boolean silentmode)
	{
		CurrentState = StartState;
		Tape = input;
		
		while(!CurrentState.equals(AcceptState) && !CurrentState.equals(RejectState))
		{
			boolean foundTransition = false;
			Transition CurrentTransition = null;
			
			if (silentmode == false)
			{
				if (CurrentSymbol>0)
				{
					System.out.println(Tape.substring(0, CurrentSymbol) + " " + CurrentState + " " + Tape.substring(CurrentSymbol));
				}
				else
				{
					System.out.println(" " + CurrentState + " " + Tape.substring(CurrentSymbol));
				}
			}
			
			
			
			

			Iterator<Transition> TransitionsIterator = TransitionSpace.iterator();
			while ( TransitionsIterator.hasNext() && foundTransition == false)
		    {
				Transition nextTransition = TransitionsIterator.next();
				if (nextTransition.readState.equals(CurrentState) && nextTransition.readSymbol == Tape.charAt(CurrentSymbol))
				{
					foundTransition = true;
					CurrentTransition = nextTransition;
				}						
		    }	
			
			if (foundTransition == false)
			{
				System.err.println ("There is no valid transition for this phase! (state=" + CurrentState + ", symbol=" + Tape.charAt(CurrentSymbol) + ")");
				return false;
			}
			else
			{
				CurrentState = CurrentTransition.writeState;
				char[] tempTape = Tape.toCharArray(); 				
				tempTape[CurrentSymbol] = CurrentTransition.writeSymbol;
				Tape =  new String(tempTape);
				if(CurrentTransition.moveDirection==true)
				{
					CurrentSymbol++;
				}
				else
				{
					CurrentSymbol--;
				}
				
				if (CurrentSymbol < 0)
					CurrentSymbol = 0;
				
				while (Tape.length() <= CurrentSymbol)
				{
					Tape = Tape.concat("_");
				}
				
				
			}			
		
			
		}
		
		if (CurrentState.equals(AcceptState))
		{
			return true;
		}
		else
		{
			return false;
		}
		
		
	}
	
	public boolean addState(String newState)
	{
		if (StateSpace.contains(newState))
		{
			return false;
		}
		else
		{
			StateSpace.add(newState);
			return true;
		}
	}
	
	public boolean setStartState(String newStartState)
	{
		if (StateSpace.contains(newStartState))
		{
			StartState = newStartState;
			return true;
		}
		else
		{
			return false;
		}		
	}
	
	public boolean setAcceptState(String newAcceptState)
	{
		if (StateSpace.contains(newAcceptState) && !RejectState.equals(newAcceptState))
		{
			AcceptState = newAcceptState;
			return true;
		}
		else
		{
			return false;
		}
		
	}
	
	public boolean setRejectState(String newRejectState)
	{
		if (StateSpace.contains(newRejectState) && !AcceptState.equals(newRejectState))
		{
			RejectState = newRejectState;
			return true;
		}
		else
		{
			return false;
		}		
	}

	public boolean addTransition(String rState, char rSymbol, String wState, char wSymbol, boolean mDirection)
	{
		if(!StateSpace.contains(rState) || !StateSpace.contains(wState))
		{
			return false;
		}
			
		boolean conflict = false;
		Iterator<Transition> TransitionsIterator = TransitionSpace.iterator();
		while ( TransitionsIterator.hasNext() && conflict == false)
	    {
			Transition nextTransition = TransitionsIterator.next();
			if (nextTransition.isConflicting(rState, rSymbol))
			{
				conflict = true;
			}
					
	    }
		if (conflict == true)
		{
			return false;
		}
		else
		{
			Transition newTransition = new Transition();
			newTransition.readState = rState;
			newTransition.readSymbol = rSymbol;
			newTransition.writeState = wState;
			newTransition.writeSymbol = wSymbol;
			newTransition.moveDirection = mDirection;
			TransitionSpace.add(newTransition);
			return true;
		}
	}
}

iam doing a mini project this semester which i was asked to implement turing machine using java language, then i found your program what a relief, it was really helpful.

that was very helpful ,thank you !

us bhai us ;")
@asayaya

us bhai us ;") @asayaya

Can you please tell how to implement this code

Us bhai us:)

…

On Sun, Oct 29, 2023, 10:52 PM aryansharma1305 ***@***.***> wrote: ***@***.**** commented on this gist. ------------------------------ us bhai us ;") @asayaya <https://github.com/asayaya> Can you please tell how to implement this code — Reply to this email directly, view it on GitHub <https://gist.github.com/NikolasTzimoulis/2846116#gistcomment-4742811> or unsubscribe <https://github.com/notifications/unsubscribe-auth/AUMZVN7VZTR3DMKBDJHSN2LYB2GG5BFKMF2HI4TJMJ2XIZLTSKBKK5TBNR2WLJDHNFZXJJDOMFWWLK3UNBZGKYLEL52HS4DFQKSXMYLMOVS2I5DSOVS2I3TBNVS3W5DIOJSWCZC7OBQXE5DJMNUXAYLOORPWCY3UNF3GS5DZVRZXKYTKMVRXIX3UPFYGLK2HNFZXIQ3PNVWWK3TUUZ2G64DJMNZZDAVEOR4XAZNEM5UXG5FFOZQWY5LFU4ZDQNBWGEYTNJ3UOJUWOZ3FOKTGG4TFMF2GK> . You are receiving this email because you commented on the thread. Triage notifications on the go with GitHub Mobile for iOS <https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android <https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub> .