I have this assignment
- Describe in words how a DTM can simulate a NTM
- Describe in wordshow a NTM can simulate a DTM
I'm working on this request and I'm crushing with the comparison.
1-I understand that every NTM can be represented by a DTM with a tree structure, that represents every step of the different possibilities of a NTM. Every step should simulate with n tapes the configuration states of the NTM with the DTM etc.
2-For this I'm a little lost, I think you can't have a DTM simulated by an NTM, the multiplicity of states allowed in NTM with guesses makes difficult to create a deterministic process o linear, ¿I'm going in the right path?.