Turing Machine & Recursive Function Simulator

Specific Tasks

1. Turing Machine Simulation System

1. Finite State Machine Simulation: Simulate the finite state automaton and its state transition process.
2. Tape and Read/Write Head Simulation: Simulate the read and write operations on the tape.
   • Evaluation Criteria: Demonstrate the dynamic execution process of the binary search algorithm in the simulation system with a given input. Provide correct results and count the tape space and steps used.

2. Recursive Function Simulation System

1. Recursive Function Call Simulation: Simulate the calling process of recursive functions.
2. Stack and Push/Pop Operations Simulation: Simulate the stack and its push and pop operations.
   • Evaluation Criteria: Demonstrate the dynamic execution process of the binary search algorithm in the simulation system with a given input. Provide correct results and count the tape space, stack space, and steps used.

3. Performance Comparison of Two Simulation Systems

1. 0/1 Knapsack Problem:
   • In the Turing Machine Simulation System: Solve using dynamic programming and branch and bound methods.
   • In the Recursive Function Simulation System: Solve using memoization and backtracking methods.
   • Evaluation Criteria: Demonstrate the dynamic solving process of the above algorithms in both simulation systems with a given input. Provide the optimal value and solution, and compare the tape and/or stack space and steps used by the algorithms.