Class TuringMachine<S,T>

java.lang.Object

org.episteme.core.mathematics.discrete.TuringMachine<S,T>

public class TuringMachine<S,T>
extends Object

Turing Machine (TM).

A TM is defined by M = (Q, Γ, b, Σ, δ, q₀, F) where:

• Q is a finite set of states
• Γ is the tape alphabet
• b ∈ Γ is the blank symbol
• Σ ⊆Γ \ {b} is the input alphabet
• δ: Q × Γ → Q × Γ × {L, R} is the transition function
• qâ‚€ ∈ Q is the initial state
• F ⊆Q is the set of accepting states

Since:

1.0

Author:

Silvere Martin-Michiellot, Gemini AI (Google DeepMind)

Nested Class Summary

Nested Classes

Modifier and Type	Class	Description
static enum	TuringMachine.Direction
class	TuringMachine.TransitionResult

Constructor Summary

Constructors

Constructor	Description
TuringMachine(S initialState, T blankSymbol)

Method Summary

Modifier and Type	Method	Description
void	addState(S state, boolean isAccepting)
void	addTransition(S fromState, T readSymbol, S toState, T writeSymbol, TuringMachine.Direction move)
boolean	run(List<T> input, int maxSteps)	Simulates the Turing Machine on the given input.

Methods inherited from class Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

TuringMachine

public TuringMachine(S initialState,
 T blankSymbol)

Method Details

addState

public void addState(S state,
 boolean isAccepting)

addTransition

public void addTransition(S fromState,
 T readSymbol,
 S toState,
 T writeSymbol,
 TuringMachine.Direction move)

run

public boolean run(List<T> input,
 int maxSteps)

Simulates the Turing Machine on the given input. Warning: May not terminate (halting problem).

Parameters:

input - initial tape content

maxSteps - maximum steps to prevent infinite loops

Returns:

true if accepted, false if rejected or max steps reached