theory salon

« first day (132 days earlier) ← previous day next day → last day (3497 days later) »

6:18 PM

from the michel ref

Actually, the halting problem for Turing machines launched on a blank tape is m-complete,
and this implies that this problem is as hard as the problem of the provability of a mathematical
statement in a logical theory such as ZFC (Zermelo Fraenkel set theory with axiom of
choice). So, when Turing machines with more and more states and symbols are studied, potentially
all theorems of mathematics will be met. When more and more non-halting Turing
machines are studied to be proved non-halting, one has to expect to face hard open problems

vzn

from tcs blog aggregator

KaHIP v0.53 -- Karlsruhe High Quality Partitioning -- User Guide

nice to see implementation of advanced theoretical concepts, which sometimes can be somewhat rare.

1 hour later…

vzn

7:27 PM

more from michel

vzn

Many universal models of computation are known: Turing machines, tag-systems, cellular
automata, Diophantine equations, etc. (see [35]). Of course, any universal model can simulate
and be simulated by any other universal model. But it is Collatz-like functions, and not
another model, that appear naturally in this study. Their unexpectedly pervasive presence
leads to wonder about the signiﬁcance of their status among mathematical beings.

p33

3 hours later…

vzn

10:03 PM

have long wondered if machine learning could be used on the collatz problem or other number theory type problems.

Q: machine learning applications in number theory

is there any research into or applications of machine learning in number theory? am also looking for (leading examples of) statistical/empirical analysis of number theory questions. also wondering if genetic algorithms in particular have ever been used in these areas. roughly related que...

somewhat inspired by this somewhat related tcs.se question. which currently has +6/-7 votes. an unusual split.

-1

Q: Why can machine learning not recognize prime numbers?

Say we have a vector representation of any integer of magnitude n, V_n This vector is the input to a machine learning algorithm. First question : For what type of representations is it possible to learn the primality/compositeness of n using a neural network or some other vector-to-bit ML mappi...