{"id":"04659cf4-6e0b-4c3f-9fd5-b2e91b8188b3","arxiv_id":"1908.09942","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A new formalism for function approximation is used to argue that no search procedure can achieve zero error on all functions and that neural architecture search might match exhaustive search only under unstated conditions.","lead":"This paper redefines function approximation as a search over sequences of simpler functions and uses that to reason about neural architecture search. It concludes that no algorithm can approximate every function perfectly, and that machine learning alone is too weak to be a universal approximator.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 2's proof conflates unbounded generative closure of elementary functions with fixed-length composition; for any finite n, E^{*,n} cannot contain all total computable functions, so the theorem's conclusion is unsupported.","rationale":"The paper's central advertised result—that under identified conditions a-ASP can match exhaustive search in polynomial time—rests on Theorem 2. The proof of Theorem 2 uses 'E can generate all computable functions' as a premise. In recursion theory this statement is true only as an unbounded closure property; the theorem's quantifier structure requires it at a fixed finite n. The paper's own Eq. (4) confines the limit statement to n→∞, so the inconsistency is internal rather than a clash with external opinion. If the theorem were merely asserting existence of a minimizer in a finite set, it would be true but would not support the comparison with 'all possible computable functions,' and it would say nothing about polynomial-time equivalence. The a-ASP section contains no construction of B(S) or runtime bound; the polynomial-time claim is asserted, not derived. These issues are load-bearing: removing the fixed-n generation assumption removes the only argument that E⊂S guarantees an optimal sequence, and no other argument is supplied. I agree with the reader that this is the weakest assumption. The proposed diagonalization check would settle whether the fixed-n premise can hold; it cannot.","tokens_in":14070,"tokens_out":6164,"duration_ms":62125,"concrete_test":"Fix a concrete Turing-equivalent basis, e.g. E = {zero, successor, projections} closed under composition and primitive recursion, and a small bound such as n = 10. Enumerate the finite set E^{*,10}; by diagonalization define a total computable function F that differs from every member of E^{*,10} at some input (e.g., F(i) = 1 - e_i(i) for the i-th enumerated program, with a total extension). This F is a total computable function not expressible as a length-≤10 sequence over E. Running the proof of Theorem 2 on this F shows the step 'E can generate all possible computable functions' fails exactly where the theorem needs it; if the theorem is instead meant to range only over E^{*,n}, then the 'all possible computable functions' phrasing is misleading and the theorem is vacuous.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing step is in the proof of Theorem 2 (Section 3.3): 'By definition, E can generate all possible computable functions. If E ⊄ S, then |S^{*,n}| < |E^{*,n}|...' This only licenses the conclusion if the generating power of E is available at the fixed, finite sequence length n used in the statement of the theorem. It is not. E is a finite set and S^{*,n} contains only finitely many sequences of length at most n, whereas the set of total computable functions is countably infinite. Every Turing-equivalent basis generates computable functions by composition of unbounded length, so for any fixed n there are total computable functions whose shortest expression in E is longer than n; the paper itself acknowledges the limit version in Eq. (4), lim_{n→∞} U(S,n) = R. Once the fixed-n version of 'E generates all computable functions' is rejected, Theorem 2 has no supporting argument: if f_o is only required to be optimal within the finite set S^{*,n}, the theorem is a trivial consequence of finiteness and does not mention 'all computable functions'; if it is required to be optimal over all computable functions of length ≤n, the set over which the optimum is taken is not E^{*,n} unless every such function admits a representation of length ≤n. The subsequent claim that a-ASP 'can potentially solve FA as well as exhaustive search, but in polynomial time' is never derived; Section 4.2 only states that by including E, a-ASP 'could have' the ability to perform as well as ASP, with no complexity argument and no demonstration that the set-builder B(S_{ASP}) can be implemented in polynomial time. Thus the central claim that the paper advertises is not established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a formal framework, the Function Approximation (FA) problem, in which approximating an input function F is recast as selecting a sequence of functions from a search space S of length at most n. It claims Theorem 1 (no computable FA procedure can approximate all continuous real-valued functions to zero error over their entire domain), Theorem 2 (if S contains the elementary functions E of a Turing-equivalent model, then for any input F there is an optimal sequence among all computable functions of length at most n), and it introduces ML, ASP, and a-ASP as solution strategies, claiming that a-ASP can potentially solve FA as well as an exhaustive search but in polynomial time. The paper is a theoretical analysis aiming to formalize Neural Architecture Search in a model-agnostic way.","tokens_in":14431,"tokens_out":5494,"duration_ms":50476,"significance":"If the claims were correct, the paper would provide a useful unifying vocabulary for NAS and automated machine learning; the reformulation of architecture search as sequence selection and the explicit connection to models of computation are attractive. The paper engages seriously with relevant literature, including no-free-lunch theorems, PAC learning, and universal approximation results, and it attempts to define search-space capacity through the information potential. However, the central theorems are not supported by the proofs as written: Theorem 1's proof is heuristic, and Theorem 2's conclusion is either trivial or rests on a false fixed-length generation premise. The a-ASP polynomial-time claim is not derived. The conceptual framework may be a seed for future work, but the paper's load-bearing formal results are not established.","major_comments":[{"comment":"The proof does not establish the theorem. The reduction to the equivalence problem of halting Turing machines is asserted without construction: given an FA instance with particular F, S, n, and sigma, it is not shown how deciding zero-error approximability would encode equivalence of two halting TMs. The cardinality remarks about finite n, sigma, or S show only that a restricted procedure cannot cover all inputs, not that no procedure can; and the treatment of uncomputable F is not a computational lower bound, since it is unclear how an uncomputable function is presented as input. Moreover, Eq. (1) defines epsilon_sigma only as a finite average, while Theorem 1 quantifies over the entire domain, which may be infinite; the statement is therefore not well-formed for general continuous functions.","section":"Section 3.2, Theorem 1"},{"comment":"Theorem 2 is not proven as stated. The premise that E can generate all possible computable functions is a statement about unbounded composition, whereas the conclusion concerns sequences of length at most a fixed finite n. For any finite n, E^{*,n} is finite, while the set of total computable functions is countably infinite, so E^{*,n} cannot contain all computable functions. If 'smallest approximation error among all possible computable functions of sequence length up to and including n' means the minimum over the finite set S^{*,n} only, then the theorem is a trivial consequence of finiteness and the condition E⊂S plays no role. If it means a global optimum over all computable functions representable in at most n steps, the premise is false. The proof's cardinality claim that E⊄S implies |S^{*,n}|<|E^{*,n}| does not imply that an optimal sequence for a given F is missing, and the paper's own limit statement in Eq. (4) only gives U(S,n)→R as n→∞. This theorem is the central result supporting the later claims about ASP and a-ASP.","section":"Section 3.3, Theorem 2 and Eq. (4)"},{"comment":"The abstract and conclusion claim that a-ASP 'can potentially solve FA as well as an exhaustive search, but in polynomial time', but no such result is proved. The set-builder function B is defined only by B(S)⊂S^{*,n}; no complexity constraint is imposed on B, and no argument shows that any B can select the optimal sequence without examining the whole space. Section 4.2 states only that a-ASP 'could have' the ability to perform as well as ASP 'by including E', and the conclusion says that existing literature 'complemented with the results from this framework' shows this ability; neither the conditions promised in the abstract nor a polynomial-time bound is stated or derived. The reference to [56] is an appeal to prior results, not a derivation within the framework.","section":"Section 4.2, a-ASP"},{"comment":"The formal apparatus is not precise enough to support the theorems. Eq. (1) defines epsilon_sigma via a sum over sigma, but sigma is later allowed to be an arbitrary subset of the domain, and Theorem 1 quantifies over the entire domain; no integral or measure is supplied for infinite sigma. The convention d(f(x),g(x))=g(x) for x not in dom(f) is inconsistent because d is required to take values in R_{\\ge 0}, whereas g(x) need not be nonnegative. In Definition 3, C(f) is a Cartesian product involving domains and images that are arbitrary sets, so it is not a well-defined quantitative capacity, and the comparison U(S1,n)=U(S2,n) as set equality in Definition 4 is asserted without a metric or measure. These imprecisions make it difficult to verify the claimed bounds.","section":"Sections 3.1 and 3.2, Definitions 1-4"}],"minor_comments":[{"comment":"The definition S^{*,n} = {(\\phi_i)_{i=1}^k | \\phi_i \\in S, k \\le n} and the assertion 'f \\in S^{*,n} \\Leftrightarrow f \\in R' are not meaningful without specifying the distinction between a sequence and the function it computes; this should be clarified.","section":"Section 3.1"},{"comment":"The phrase 'the approximation error of a function f to a function g is a procedure which outputs 0 if ...' conflates a numeric value with a procedure; Eq. (1) defines a value, not a procedure, so the wording should be aligned.","section":"Section 3.2, Definition 1"},{"comment":"The paper says it will consider continuous, real-valued functions and then, beginning in Section 3.3, only computable functions; the relationship between these restrictions should be stated explicitly, since not all continuous functions are computable.","section":"Section 3.1 and 3.3"},{"comment":"There are several typographical and referencing issues: the citation line contains a stray 'with', the set notation in Section 4.2 for the sequence of errors is malformed, and some references are cited only in the text without appearing in the bibliography in a consistent format.","section":"Throughout"}],"recommendation":"reject","confidential_remarks":"For the editor: the paper is a short theoretical manuscript whose central formal results are not supported by the proofs. Theorem 2, on which the ASP and a-ASP claims rest, is either trivial under an internal reading or false under a global reading, and the a-ASP claim is substantially overstated relative to what is proved. The paper contains a promising conceptual direction and engages the relevant literature, but I do not see a revision within the manuscript's scope that would repair the main proof; the framework would need to be substantially reworked."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is an interesting way to frame NAS, but the main theorems don't hold up. I wouldn't cite the results as established, though the framework might be worth a look if you work on NAS theory.\n\nWhat is new: the FA formulation—searching over S^{*,n} for a sequence that minimizes approximation error—and the related information capacity/potential definitions. The paper organizes known results (no-free-lunch, undecidability) into a common language, and the discussion of ML as a singleton search space versus ASP as exhaustive search is a fair way to think about the landscape. The writing is clear and the citations are appropriate.\n\nThe soft spot is Theorem 2. The proof uses 'E can generate all computable functions' to claim that if E is not in S, then |S^{*,n}| < |E^{*,n}|, so some optimal f_o must lie outside S^{*,n}. This only goes through if every computable function can be expressed in E using at most n functions. That is false for fixed n: E is finite, E^{*,n} is finite, and the set of total computable functions is countably infinite. The paper itself states the correct limit version in Eq (4), lim_{n→∞} U(S,n)=R, which shows the fixed-n claim is exactly what needs proof. So Theorem 2 is not proven as stated. The a-ASP claim that including E lets a-ASP 'potentially solve FA as well as exhaustive search, but in polynomial time' is never derived; Section 4.2 only says it 'could have' that ability, and no complexity argument or construction of the set-builder B appears.\n\nTheorem 1 is also loosely argued: the finite-σ part is a cardinality observation, not undecidability, and the reduction to halting TM equivalence is not stated carefully. The result itself is classical, so the paper's contribution reduces to the framework, not new impossibility results.\n\nBottom line: the framework is a reasonable lens, but the advertised results don't survive. I would not cite it for the theorems. It deserves a serious referee—if the authors are willing to rework the proofs and scale back the claims, there is something salvageable—but as it stands, reject. For a reading group, it's a nice case study in how quickly a plausible theory overclaims in NAS.","headline":"A well-intended reformulation of NAS as function approximation, but Theorem 2 doesn't prove what it claims and the polynomial-time a-ASP result never follows—treat it as an interesting failed attempt, not a usable theory.","tokens_in":14946,"tokens_out":3739,"would_cite":false,"duration_ms":36469,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that no computable procedure can approximate every continuous function exactly, and that bounded-length approximation becomes optimal whenever the search space contains the elementary functions of a Turing-complete model.","keywords":["function approximation","neural architecture search","search space","computability","Turing equivalence","information potential","machine learning theory","architecture search problem"],"falsifier":"Set $n=1$, let $E$ be a finite set whose one-step sequences cannot express $\\sin$, and let $S$ contain $E$ but not $\\sin$. The sequence $(\\sin)$ has zero approximation error to $F=\\sin$ and is a computable sequence of length one, yet no member of $S^{\\star,1}$ attains zero error, so the optimal sequence promised by Theorem 2 does not exist unless 'computable functions of length up to $n$' is redefined as 'functions expressible from $E$ in at most $n$ steps.'","tokens_in":13882,"feed_emoji":"🧠","tokens_out":11157,"duration_ms":111676,"temperature":0.7,"pith_summary":"The paper tries to give automated architecture search a theoretical foundation by recasting function approximation as a search problem: given a target function $F$, a search space $S$, a length bound $n$, and sample points $\\sigma$, find the sequence of functions from $S$, of length at most $n$, whose average error to $F$ is smallest. It argues that no computable procedure can solve this problem exactly for all continuous real-valued functions, but that a globally minimal error is achievable for each $F$ if $S$ contains the elementary functions of a Turing-complete model. The paper then classifies machine learning, exhaustive architecture search, and approximate architecture search as solution strategies, concluding that the first is weak, the second is optimal but intractable, and the third can in principle match the second in polynomial time. The reason to care is that these bounds would explain when automated machine learning should work at all and what a search space must contain to be provably good.","feed_headline":"No procedure can approximate every function to zero error","feed_subtitle":"Search spaces that include a model's elementary functions can hit the best achievable error, the paper argues.","key_machinery":"The load-bearing mechanism is the representation of a model as a finite set of elementary functions $E$ together with a composition operation, so that any candidate solution is a sequence $(\\varphi_{i_1},\\ldots,\\varphi_{i_k})$ of length $k \\leq n$. The paper defines the approximation error $\\varepsilon_\\sigma(f,F)$ as the average distance to $F$ on a sample set $\\sigma$, the information capacity $C(f)$ of a sequence as the Cartesian product of its domains, parameters, and ranges, and the information potential $U(S,n)$ as the union of $C(f)$ over all sequences of length at most $n$ in $S$. This last quantity is what lets the paper compare search spaces without fixing a target function, and it is the quantity that remains unchanged when moving from exhaustive ASP to approximate a-ASP, supporting the claim that a-ASP can match ASP if $E \\subset S$.","core_discovery":"The paper's central claim is threefold. First, the FA problem, which asks for the length-bounded sequence over a search space that minimizes the approximation error to a target, is a faithful reformulation of what automated machine-learning pipelines try to do. Second, Theorem 1 states that no computable procedure can solve FA for all continuous real-valued functions with zero error across the whole domain, because uncomputable targets can only be approximated, and deciding whether a computable target has an exact representation reduces to an undecidable halting-equivalence question. Third, Theorem 2 states that if the search space $S$ contains the finite set $E$ of elementary functions of some Turing-equivalent model, then for every $F$ there exists a sequence in $S^{\\star,n}$ whose approximation error is the smallest among all computable sequences of length at most $n$. From these, the paper infers that a fixed architecture makes machine learning a weak FA solver, that exhaustive architecture search is the strongest but intractable solver, and that a pruned approximate version, a-ASP, can solve FA as well as exhaustive search in polynomial time when $E$ is included and the set-builder $B$ is chosen well.","pith_inferences":["The paper leaves the length bound $n$ fixed; an immediate extension is to let $n$ grow with the target's complexity, which would connect the framework to resource-bounded Kolmogorov complexity and program synthesis.","The information potential $U(S,n)$ is a new capacity measure distinct from VC dimension; a testable extension would be to compute $U$ for standard cell-based NAS search spaces and compare it with observed search difficulty.","Because the paper sets aside data selection, a natural next step is to study how the sample subset $\\sigma$ controls the achievable error; a minimax analysis over $\\sigma$ could turn the framework into a theory of data-efficient architecture search."],"forward_implications":["No automated architecture search system can approximate every continuous function to zero error, so some nonzero error is unavoidable for any fixed finite search budget.","Including the elementary functions of the underlying model in the search space is a design principle that guarantees the existence of a best sequence for every target at each length bound.","Machine learning with a fixed architecture is inherently weak as a general solver, because a single-function search space cannot tell whether a better architecture exists.","Exhaustive architecture search is the strongest solver, but its exponentially growing space makes it unusable in practice.","Approximate architecture search can match exhaustive search in polynomial time if its search space contains the elementary functions and its pruning rule respects the information potential."],"supporting_citations":[{"why":"Establishes that determining how to factor a function into elementary functions is undecidable, supporting the impossibility theorem.","marker":"[11]"},{"why":"Shows continuous multivariate functions have exact superpositions of univariate functions, motivating the sequence formulation.","marker":"[24]"},{"why":"Extends Kolmogorov's superposition result, used to note exact representations exist when univariate functions are in $S$.","marker":"[34]"},{"why":"Proof that neural nets are Turing universal, giving a concrete instance of an elementary-function set $E$.","marker":"[31]"},{"why":"Shows Turing computability with neural nets, supporting the Turing-equivalence premise.","marker":"[45]"},{"why":"Analyzes the computational power of neural nets, reinforcing their role as a model of computation.","marker":"[46]"},{"why":"Supplies the universal function used as the limiting universal approximator in the information-potential discussion.","marker":"[41]"},{"why":"No-free-lunch results used to argue fixed architectures have equivalent average performance, making ML a weak FA solver.","marker":"[55]"},{"why":"Coevolutionary free-lunch results used to justify that set-builder choices let a-ASP differ in performance.","marker":"[56]"}],"fun_headline_variants":["No perfect function approximation for all functions","Neural architecture search cannot solve all functions exactly","Elementary functions in search space hit optimal error","Polynomial-time architecture search possible in certain cases","Machine learning can't approximate every function to zero error"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The optimality theorem assumes that the finite set of elementary functions $E$ can generate every computable function using no more than the fixed bound $n$ of composition steps; standard recursion theory gives no such bound, so if this premise fails the theorem's conclusion need not hold.","fun_headline_variants_meta":{"raw":{"variants":["No perfect function approximation for all functions","Neural architecture search cannot solve all functions exactly","Elementary functions in search space hit optimal error","Polynomial-time architecture search possible in certain cases","Machine learning can't approximate every function to zero error"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000315,"raw_usage":{"total_tokens":1821,"prompt_tokens":1013,"completion_tokens":808,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":629,"completion_tokens_details":{"reasoning_tokens":738}},"tokens_in":629,"tokens_out":808,"duration_ms":8529,"temperature":1.0,"reasoning_tokens":738,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:57:21.058464+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Set $n=1$, let $E$ be a finite set whose one-step sequences cannot express $\\sin$, and let $S$ contain $E$ but not $\\sin$. The sequence $(\\sin)$ has zero approximation error to $F=\\sin$ and is a computable sequence of length one, yet no member of $S^{\\star,1}$ attains zero error, so the optimal sequence promised by Theorem 2 does not exist unless 'computable functions of length up to $n$' is redefined as 'functions expressible from $E$ in at most $n$ steps.'","supporting_citations":[{"cited_title":"American Jour- nal of Mathematics 58, 345–363 (1936)","cited_arxiv_id":null,"evidence_quote":"Establishes that determining how to factor a function into elementary functions is undecidable, supporting the impossibility theorem."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows continuous multivariate functions have exact superpositions of univariate functions, motivating the sequence formulation."},{"cited_title":"S.: Turing universality of neural nets (revisited)","cited_arxiv_id":null,"evidence_quote":"Proof that neural nets are Turing universal, giving a concrete instance of an elementary-function set $E$."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Shows Turing computability with neural nets, supporting the Turing-equivalence premise."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Analyzes the computational power of neural nets, reinforcing their role as a model of computation."},{"cited_title":"MIT Press, Cambridge, MA (1987)","cited_arxiv_id":null,"evidence_quote":"Supplies the universal function used as the limiting universal approximator in the information-potential discussion."},{"cited_title":"IEEE Transactions on Evolutionary Computation 9, 721–735 (2005)","cited_arxiv_id":null,"evidence_quote":"Coevolutionary free-lunch results used to justify that set-builder choices let a-ASP differ in performance."}],"review_version":1}