We construct a first-order formula φ such that all finite models of φ are non-narrow rectangular grids without using any binary relations other than the grid neighborship relations. As a corollary, we prove that a set A ⊆ ℕ is a spectrum of a formula which has only planar models if numbers n ∈ A can be recognized by a non-deterministic Turing machine (or a one-dimensional cellular automaton) in time t (n) and space s (n), where t (n)s (n) ≤ n and t (n), s (n) = Ω(log(n)).
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.