Structured Frequency Algorithms

摘要: B.A. Trakhtenbrot proved that in frequency computability (introduced by G. Rose) it is crucially important whether the exceeds \(\frac{1}{2}\). If does then only recursive sets are frequency-computable. not exceed \(\frac{1}{2}\) a continuum of Similar results for finite automata were E.B. Kinber and H. Austinat et al. We generalize notion demanding specific structure correct answers. show if this described terms projective planes even \(O(\frac{\sqrt{n}}{n})\) ensures recursivity computable set. also with overlapping structures cannot be significantly decreased. introduce graph computation prove sufficient conditions \(G\) such can \(G\)-computed.