most recent 30 from http://mathoverflow.net 2013-05-24T22:03:57Z http://mathoverflow.net/feeds/user/11426 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/85975/statements-outside-of-the-kleene-hierarchy twiz 2012-01-18T09:49:18Z 2012-01-18T14:50:56Z

<p>I take a list of $2*m$ natural numbers {$n_k$}. I encode them in some way together to a single bit sequence. Now I feed this bit sequence to a Turing machine $T$. Call the statement "For all $n_1$, there exists an $n_2$ so that for all $n_3$, there exists an $n_4$... so that for all $n_{2*m-1}$, there exists an $n_{2*m}$ so that the Turing machine $T$ halts." statement $S_m$.</p> <p>Now: Can statements of the form "There exists a $m$ so that statement $S_m$ is true" be, in general, formalized within the general notation for number-theoretic statements; does it lie in the Kleene Hierarchy?</p>

http://mathoverflow.net/questions/71135/probability-that-a-turing-machine-is-universal twiz 2011-07-24T17:00:31Z 2011-07-24T23:36:47Z

<p>I choose a Turing machine T with n states and an input tape at random.</p> <p>What can be proven about the probability P_A(n) that it is not decidable whether T will halt for a particular input? What can be proven about P_B(n) that T is universal, that means that there exists an algorithm that takes an obvious encoding of an arbitrary Turing machine A (without input tape) and transforms it into an input for my random Turing machine, so that T halts with this input if and only if A halts? In particular: Is it known that P_A(n) is strictly smaller than P_B(n) for some n?</p>

http://mathoverflow.net/questions/66730/algebraic-structures-of-greater-cardinality-than-the-continuum twiz 2011-06-02T13:20:33Z 2011-06-02T14:26:11Z

<p>Are there interesting algebraic structures whose cardinality is greater than the continuum? Obviously, you could just build a product group of $\beth_2$ many groups of whole numbers to get to such a structure, but the properties of this group seem to be not very different from those you get when you just put together $\beth_1$ many whole number groups here.</p>

http://mathoverflow.net/questions/71135/probability-that-a-turing-machine-is-universal twiz 2011-07-25T10:32:07Z 2011-07-25T10:32:07Z

I want to ask whether there exists a Turing machine that always halts and gives the correct answer, not whether that is provable in some axiomatization. I don't know if I understand your first question: My input tape has finite length (it exists in addition to the working tape, and it can be assumed that it is impossible to modify it), and I want to know whether it can be decided for all initial values on the input tape if it halts. If the input tape was always zero, the program would always halt or not halt, so there must exist a program that tells the correct result.