Hacker News new | past | comments | ask | show | jobs | submit login

A 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

[1] https://cs.stackexchange.com/questions/63136/does-the-amount...




Consider applying for YC's W25 batch! Applications are open till Nov 12.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: