3 ms·

Turing Machine Notation and Normal Form

28 points by nickdrozd 6y ago

qsort 6y ago
I don't want to demean your work in any way, but what exactly is the problem you are trying to solve? You certainly already know that determining whether two machines are extensionally different is undecidable, so, what kind of ambiguity your choice of a normal form would eliminate? It's not like people are emailing Turing machines back and forth, it's mostly just a definition.
- nickdrozd 6y ago
  I got involved with Turing machine searching after reading Scott Aaronson's recent Busy Beaver survey [1]. This definition of normal form solves three problems. 1. One question about busy beavers is: is there a unique halting n-state TM of maximal runtime? The answer is obviously no, since every program can be modified by shuffling states, etc. So the question needs some caveat to exclude uninteresting variations. There doesn't seem to have been a good definition of that up to now, where "good" means "precise and reliable". 2. If you are searching for certain Turing machines, like busy beaver candidates, one strategy would be to generate all possible programs and then filter for certain properties. This definition makes for an easy filter. It might even be possible to define with a regexp. 3. Emailing. Yes, believe it or not, I personally have emailed Turing machine programs to other people in the past few months. Of course, I'm not saying that these are particularly important problems to solve, but if you search for Turing machines, they're problems you might deal with. Check out this historical list of busy beaver candidate programs [2]. [1] https://www.scottaaronson.com/blog/?p=4916 https://www.scottaaronson.com/blog/?p=4916 [2] http://www.logique.jussieu.fr/~michel/ha.html http://www.logique.jussieu.fr/~michel/ha.html
  - qsort 6y ago
    Ok, now I understand what you are trying to do. I had no idea there was active research on that topic, I was lacking a piece of context to figure out why would someone care. Your definition is equivalent to saying "TMs are not meaningfully different if their transition graphs are isomorphic", is that correct?

28 points by nickdrozd 6y ago

I don't want to demean your work in any way, but what exactly is the problem you are trying to solve? You certainly already know that determining whether two machines are extensionally different is undecidable, so, what kind of ambiguity your choice of a normal form would eliminate? It's not like people are emailing Turing machines back and forth, it's mostly just a definition.

nickdrozd 6y ago
I got involved with Turing machine searching after reading Scott Aaronson's recent Busy Beaver survey [1]. This definition of normal form solves three problems. 1. One question about busy beavers is: is there a unique halting n-state TM of maximal runtime? The answer is obviously no, since every program can be modified by shuffling states, etc. So the question needs some caveat to exclude uninteresting variations. There doesn't seem to have been a good definition of that up to now, where "good" means "precise and reliable". 2. If you are searching for certain Turing machines, like busy beaver candidates, one strategy would be to generate all possible programs and then filter for certain properties. This definition makes for an easy filter. It might even be possible to define with a regexp. 3. Emailing. Yes, believe it or not, I personally have emailed Turing machine programs to other people in the past few months. Of course, I'm not saying that these are particularly important problems to solve, but if you search for Turing machines, they're problems you might deal with. Check out this historical list of busy beaver candidate programs [2]. [1] https://www.scottaaronson.com/blog/?p=4916 https://www.scottaaronson.com/blog/?p=4916 [2] http://www.logique.jussieu.fr/~michel/ha.html http://www.logique.jussieu.fr/~michel/ha.html
- qsort 6y ago
  Ok, now I understand what you are trying to do. I had no idea there was active research on that topic, I was lacking a piece of context to figure out why would someone care. Your definition is equivalent to saying "TMs are not meaningfully different if their transition graphs are isomorphic", is that correct?