A functional implementation of a Turing Machine simulator in Scala, including a Universal Turing Machine (UTM)!
Live Demo: Turing Machine Simulator (Ctrl+click to open in new tab)
This project implements a single-headed, single-tape Turing machine capable of:
- Processing machine descriptions from JSON files
- Simulating standard Turing machines
- Operating as a Universal Turing Machine
- Computing time complexity (bonus feature)
- 🎯 Single-headed, single-tape Turing machine implementation
- 📝 JSON-based machine configuration
- 🔄 Step-by-step visualization of the machine's execution
- ⚡ Adjustable execution speed (up to 10x)
- 🛑 Error detection and handling for invalid inputs or configurations
- Unary Addition: Computes the sum of two unary numbers
- Palindrome Checker: Determines if input is a palindrome
- 0ⁿ1ⁿ Language: Validates if input matches format 0ⁿ1ⁿ
- 02ⁿ Language: Validates if input matches format 02ⁿ
- Universal Turing Machine: Simulates the unary addition machine
- Time complexity analysis for executed algorithms
- Visual representation of computational steps
- Complexity classification (O(1), O(n), O(n log n), O(n²), O(n³))
The web interface (built with Streamlit) provides:
- Interactive machine selection
- Real-time tape visualization
- Speed control
- Dark mode UI
- Responsive design
- Scala 3
- Functional programming principles
- Streamlit (web interface)
- Play JSON for configuration parsing
- Pure functional implementation
- Immutable data structures
- Pattern matching for state transitions
- Type-safe representation of machine configurations
- Scala 3.x
- sbt
sbt run "machines/unary_add.json" "1+1="
For any questions or feedback about the project, feel free to reach out!
- Alan Turing, for his groundbreaking work in computer science
- 42 School, for the challenging project subject
- The Scala community for excellent tooling and documentation
Happy computing! 🧮✨