3 ms·
BB(n) refers to Turing machines that have n states and 2 symbols. The version with two arguments lets you specify the number of states and the number of symbols
by FartyMcFarter 3y ago
BB(n) refers to Turing machines that have n states and 2 symbols. The version with two arguments lets you specify the number of states and the number of symbols respectively.
So BB(n) = BB(n, 2) .
- olddustytrail 3y agoAre they fundamentally different or could you always map a BB(x,y) to a BB(z), where presumably z is much larger than x?
- abetusk 3y agoA universal Turing machine can be made with two symbols, so in the sense that there's a reduction from one to the other, yes. I would say a better question is to determine if there's some type of polynomial time/space reduction from BB(x,y) to BB(z), in construction and runtime. I suspect yes though I wouldn't be able to rattle off a proof without a lot of effort. See [1] which might answer this question. [0] https://en.wikipedia.org/wiki/Universal_Turing_machine https://en.wikipedia.org/wiki/Universal_Turing_machine [1] https://cs.stackexchange.com/questions/63136/does-the-amount-of-symbols-a-turing-machine-has-affect-what-computations-it-can https://cs.stackexchange.com/questions/63136/does-the-amount...