Bootstrapping the Primitive Recursive Functions by 47 Colors

Authors

  • Søren Riis

DOI:

https://doi.org/10.7146/brics.v1i25.21641

Abstract

I construct a concrete coloring of the 3 element subsets of N. It has the property that each homogeneous set {s_0, s_1, s_2, ..., s_r}, r >= s_0 - 1 has its elements spread so much apart that F_{omega}(s_i) < s_{i+1} for i = 1, 2, ..., r -1. It uses only 47 colors. This is more economical than the approximately 160000 colors used by Ketonen and Solovay.

Downloads

Published

1994-08-03

How to Cite

Riis, S. (1994). Bootstrapping the Primitive Recursive Functions by 47 Colors. BRICS Report Series, 1(25). https://doi.org/10.7146/brics.v1i25.21641