**Abstract**

A problem in P (sorting integers) is compared to a problem in PSPACE (John Nash's Hex game), and it is shown that a Turing Machine that is capable of infinite computation in finite time will demonstrate different behavior in the two cases, thereby indicating that P is a separate class from PSPACE.

**I - Sorting Integers**

If we take a finite integer i, there are i factorial (i!) ways it can be sorted. Thus, for any integer we can list out possible solutions for sorting this integer (from smallest to largest, etc.) in a finite time. If we had an Turing Machine that could go over all integers from 0 to infinity in finite time, this machine could, for every integer, list out all possible sorting combinations for that integer. The end result of this, for each integer up to infinity, would be still a countably infinite set of integers, that is, the solutions (different ways to sort each integer i) can be listed in a countable manner. Hence, P problems are countable, in the sense defined by Georg Cantor in the 19th century. So our Turing Machine can here list out all possible solutions.

**II - John Nash's Hex game**

The game Hex, invented by John Nash at Princeton (wiki link here) is a game where players try to place pieces on a (depending upon implementation) 14X14 board filled with hexagonal squares. The player that makes a connected path from left to right across the board wins. This has been shown to be PSPACE complete, namely, that for a given player position, it is a PSPACE-hard problem to determine if that player can win. If we think of an infinite Hex board (both along the vertical and horizontal), we can apply the same infinite Turing Machine to list out possible solutions (paths across the board going from left to right), all the way down the board. We could label all hexagonal cells in the neighborhood about a possible path with some convention, say, 1, 0,-1, with 1 meaning a hexogon just forward and above the current cell location, 0 as the hexagon just forward of the current cell location, and -1 as the cell just forward and downward of the current cell location, such that all paths across the board from start position over an infinite number of cells to the end position with numbers like 0,1,-1,0... One could then draw a diagonal swath across a given number of paths, and change some of the labels, making these paths become different paths than they were originally, and, after that, one would have changed the listing of possible paths (solutions) over the infinite hex board. This is nothing but Cantor's diagonalization argument for the real numbers, which are not countable. In other words the list of possible solutions for an infinite Hex board is in this manner not countable (listable), i.e. our Turing Machine cannot here list out all possible solutions.

**III - Conclusions**

By taking a P problem and showing that the listing of its solutions is countable, and taking a PSPACE problem and showing that the listing of its solutions is not countable, we see, by use of a Turing Machine capable of infinite computation in a finite time, that these problem domains are distinguishable in this manner when one is dealing with the asyomtotic (infinite) case for these problems. This can be argued to be supporting evidence for the proposition that P is separate from PSPACE. One could examine Hamiltonian circuits which are NP-complete and make a similar argument to support distinguishing P from NP. Of course this does nothing to comment upon whether or not PSPACE and NP are separate, but the argument to support separating P from PSPACE could be extended to Hamiltonian circuits to make a further circumstantial argument that P should be separated from NP. In any event, this argument should show the fruitful nature of examining Turing Machines of infinite power when dealing with such problems in complexity theory, which is presently being done by some researchers.

March 19, 2014

Asheville, North Carolina