@glebunov

2 weeks ago

I had lectures on turing machines just last semester, so here are some notes on formal TMs (according to my knowledge). If you care about formal TMs as long as the TM works for your use cases / programs is up to you ofc)) - The alphabet usually contains at least a NULL symbol and a SEPARATOR symbol. beyond the input data the tape is filled with NULL to infinity - There is one head per tape but there may be multiple tapes. this makes certain programs easier to write but a single head does not restrict computational power - some TMs implement a STANDSTILL move next to left and right, this does not affect computational power but makes certain programs easier to write - non determinism increases the computational power of a TM, this is achieved using multiple instructions for a single STATE+READ tuple and splitting exwcution in parallel branches - a formal TM only halts and accepts when it reaches the halting state. a missing case does not equal an accepting halt but rather a NOOP. In a single tape TM this inevitably leads to the machine getting stuck and never halting. This behaviour is actually important regarding computability and the halting problem

7 |