Jump to content

Talk:Turing Tumble

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

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)[reply]

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.

Appreciative user (talk) 11:39, 28 September 2021 (UTC)[reply]