Talk:Turing Tumble
Add topicLatest comment: 4 years ago by Appreciative user in topic Turing complete vs PSpace- and P-complete
 | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||
| ||||||||
 | The following Wikipedia contributor has declared a personal or professional connection to the subject of this article. Relevant policies and guidelines may include conflict of interest, autobiography, and neutral point of view. |
Turing complete vs PSpace- and P-complete
[edit]The introduction has two contradictory statements: the game is Turing complete, and the game is in PSPACE. The second reference for the latter says it's "P-complete" which might mean PSPACE but is more commonly used to mean complete problems for PTIME under e.g. logspace reductions. A quick look at the references did not clarify this (for me) but maybe someone who has looked at this can correct the article. 73.149.246.232 (talk) 23:19, 10 May 2020 (UTC)
Response - The second reference shows that it is PTIME-complete under logspace reductions, and shows that if an exponential number of marbles is allowed, it is PSPACE-complete. So, there is no contradiction.