Запыт аб тым, ці ўсе розныя варыянты машын Цьюрынга эквівалентныя па вылічальных магчымасцях, з'яўляецца фундаментальным пытаннем у галіне тэарэтычнай інфарматыкі, асабліва ў рамках вывучэння тэорыі складанасці вылічэнняў і магчымасці рашэння. Каб вырашыць гэтую праблему, вельмі важна ўлічваць прыроду машын Цьюрынга і канцэпцыю вылічальнай эквівалентнасці.