{"id":"840689bb-e35b-46bd-8800-a56d444f1e78","arxiv_id":"2411.15008","paper_version":2,"verdict":"REJECT","confidence":"HIGH","novelty_score":2.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"The paper restates known results to argue that evolutionary automata accept all languages by hard-coding them, but admits the construction fails for undecidable languages.","lead":"This paper proposes evolutionary automata, infinite sequences of automata that evolve, and claims they can accept any language, including undecidable ones. The proof works by pre-coding each accepted word into the sequence, which for undecidable languages cannot actually be built.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5.3 is nonconstructive: the component sequence is defined from L itself, so for undecidable L no effective enumeration exists and the inference to 'solving' undecidable problems fails; Remark 5.4 concedes the components cannot be constructed.","rationale":"The reader's weakest assumption identifies the same load-bearing point: the sequence of components is chosen without an effective procedure to enumerate an arbitrary language L. My reading agrees. I add one nuance: Theorem 5.3 is not necessarily false under the paper's permissive definition of an evolutionary automaton as an arbitrary (possibly infinite, non-effectively given) sequence. As a pure set-theoretic statement, any countable language can be paired with singleton-accepting automata, and terminal-mode union yields L. The failure is in the inference from this existence statement to 'evolutionary computation can solve Turing-machine undecidable problems.' A computation or an evolutionary algorithm must be an effective object; the proof gives no method to generate the components, and the paper's Remark 5.4 concedes exactly this. Theorems 5.1 and 5.2 are not affected, since their enumerations are computable; the weakness is specific to the universal claim and its interpretation. Credit should be given for the explicit limitations in Remark 5.4 and the conclusion, but those limitations undercut the advertised contribution. Hence I do not move the reader's REJECT verdict; the central positive claim remains unsupported as stated.","tokens_in":18559,"tokens_out":5127,"duration_ms":53828,"concrete_test":"Restate Theorem 5.3 for effectively presented EFAs, requiring the sequence t -> A[t] to be generated by a Turing machine (or by an explicit evolutionary process), and compute the class TL(EFA_eff). If TL(EFA_eff) is contained in the recursively enumerable languages, the original theorem's 'all languages' result depends essentially on dropping effective presentation, confirming that the undecidability claim is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central result, Theorem 5.3, constructs an EFA for a language L by taking, for each w in L, a finite automaton A_w that accepts exactly w, and then 'taking any sequence E = {A[t] = A_w, w in L}'. This only works if such a sequence is available as an object. For infinite L this requires an enumeration of L; for undecidable L, no effective enumeration exists. Thus the proof is nonconstructive and circular: acceptance of u is determined by whether A_u occurs in E, which is determined by u in L, so membership is presupposed rather than computed. Nothing in the terminal-mode definition supplies an effective way to find the accepting component. The paper itself states in Remark 5.4 that for undecidable non-recursive languages 'we cannot construct such finite automata, thus we will not know that this specific EFA encodes the language', and Section 8 admits the membership problem for undecidable languages is 'not done yet'. Consequently Theorem 5.3 may hold as a set-theoretic existence statement about arbitrary sequences of automata, but it does not establish that evolutionary computation can solve TM-undecidable problems. The theorem's expressiveness is an artifact of allowing a noncomputably chosen infinite family of components.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces evolutionary automata, defined as sequences of component automata E[t] that process successive population generations, and studies their terminal-mode acceptance. The main claim is Theorem 5.3: the terminal languages of evolutionary finite automata coincide with the class of all languages over a finite alphabet, from which the paper infers that evolutionary computation can solve Turing-machine undecidable problems. The paper also compares evolutionary automata with other super-Turing models, proposes a complexity hierarchy (p-, e-, a-, i-decidable), and gives a new proof of asymptotic convergence for evolutionary algorithms with elitism and complete variation operators.","tokens_in":18821,"tokens_out":6426,"duration_ms":56891,"significance":"If Theorem 5.3 were constructive, it would establish a striking super-Turing expressiveness result for a simple evolutionary model, with consequences for the theoretical foundations of evolutionary computation. The paper is also useful in explicitly distinguishing terminal acceptance from recursive decidability and in situating evolutionary automata among other super-Turing frameworks. However, the central proof is nonconstructive and circular, as the paper itself concedes in Remark 5.4 and Section 8, so the claimed consequence that evolutionary computation can solve undecidable problems is not established. The framework may have pedagogical value, but the main contribution does not survive scrutiny.","major_comments":[{"comment":"The proof defines, for each word w in L, a finite automaton A_w accepting exactly w, and then takes 'any sequence E = {A[t] = A_w, w in L}' of such automata. For an infinite language L this requires an enumeration of L to build the sequence, and for an undecidable L no effective enumeration exists. More fundamentally, the construction is circular under the terminal-mode semantics of Definition 5.1: an input u is accepted by E iff some component A_u accepting u occurs in E, which is determined by u in L. Thus membership in L is presupposed by the choice of E rather than computed by it.","section":"Section 5, Theorem 5.3"},{"comment":"Remark 5.4 explicitly states that for undecidable non-recursive languages 'we cannot construct such finite automata, thus we will not know that this specific EFA encodes the language,' and Section 8 concedes that constructing input strings for undecidable languages 'requires to solve the membership problem for undecidable languages' and is 'not done yet.' These statements directly undermine the inference drawn from Theorem 5.3 that evolutionary computation can solve Turing-machine undecidable problems. The theorem at best provides a nonconstructive set-theoretic existence statement about arbitrary infinite sequences of finite automata, not a demonstration that any effective evolutionary process decides membership.","section":"Section 5, Remark 5.4 and Section 8"},{"comment":"The definition of evolutionary automata intentionally leaves unspecified how the component automata E[t] evolve from generation to generation, and Remark 4.4 states that 'that is not needed for the proof of expressiveness of evolutionary automata.' This is another indication that the expressiveness claim of Theorem 5.3 is an artifact of freely choosing the component sequence to match the target language. Without a specification of how E[t] is produced or selected, the model does not supply an algorithm that could be said to solve a problem, so the super-Turing consequences drawn from the theorem do not follow.","section":"Section 4, Remark 4.4"}],"minor_comments":[{"comment":"The proof of Theorem 3.1 is essentially a restatement of the assumptions: if variation operators are complete, then by definition every search point, including a global optimum, is reached with positive probability, and infinite time plus elitism then guarantee retention of the optimum. The argument is correct but tautological; the paper should identify what new content beyond the earlier proofs it cites is being claimed.","section":"Section 3.1, Theorem 3.1"},{"comment":"There are several typos, including 'langauges' for 'languages' in the title of Corollary 5.4 and 'vey simple' for 'very simple' in Remark 5.4; these should be corrected.","section":"Corollary 5.4 and Remark 5.4"},{"comment":"The acceptance condition 'there is a number t' should specify whether the component automaton must terminate on the given input or merely reach an accepting state while possibly continuing; the proof of Theorem 5.3 uses transducers that output non-accepted words to the next component, so a formal output convention is needed.","section":"Definition 5.1 and proof of Theorem 5.3"},{"comment":"The text uses 'obvolute' where 'convoluted' is intended, and 'Meale/Moore' should be 'Mealy/Moore' throughout; these spelling errors should be fixed.","section":"Remarks 4.2 and 4.3"},{"comment":"The classes p-, e-, a-, i-decidable are listed without proof of separation or of membership of standard problems; as they stand, they are descriptive categories rather than a complexity theory, and this should be acknowledged explicitly.","section":"Section 7, Definition 7.1"}],"recommendation":"reject","confidential_remarks":"The central result of this manuscript is not defensible as stated. Theorem 5.3's construction presupposes the target language, and the author's own Remark 5.4 and Section 8 concede that the components for undecidable languages cannot be constructed. This is a load-bearing circularity that cannot be repaired within the manuscript's current scope. In addition, the paper overlaps substantially with the author's prior publications [6,7,8,9,12,15,17]; the genuinely new material here is largely speculative. I recommend rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Mark, here's the take on Eberbach's 'Evolutionary Automata and Deep Evolutionary Computation.' The paper's central claim — that evolutionary finite automata accept every language over Σ, including undecidable ones — is a nonconstructive hardcoding, and the author says so himself. The sequence of component automata is defined by enumerating the language; for an undecidable L there is no effective enumeration, so the 'solution' presupposes membership rather than computing it. Remark 5.4 concedes the components cannot be constructed for non-recursive languages, and Section 8 admits the membership problem is 'not done yet.' So the inference from Theorem 5.3 to 'evolutionary computation can solve TM-undecidable problems' does not go through.\n\nWhat's genuinely useful: the paper is honest about the limitation, and the proof of Theorem 3.1 (convergence in the limit with elitism and complete variation) is a clean, simple argument, even if the result is known. The survey of super-Turing models in Section 6 is a reasonable orientation. The 'deep evolutionary computation' label is just a rebranding, though.\n\nThe soft spots are the load-bearing ones. Theorem 5.3 is circular in exactly the way the reader's report says: A_u accepts u by construction, and u ∈ L iff A_u appears in the sequence, so acceptance is encoded in the index. For finite or recursively enumerable L, you can effectively build the sequence; for undecidable L, you cannot, and the paper admits it. The novelty is low: the EFA model and the all-languages expressiveness theorem are in Burgin & Eberbach 2012 (ref [8]); the new material is mostly conjecture about other models. Corollary 5.4 and the claim that EFA, o-machines, and interaction machines are equally expressive rest on the same nonconstructive footing.\n\nWho's this for? Readers interested in hypercomputation speculation or in seeing a clear example of why infinite component sequences don't buy you decidability. It could be a discussion paper, but it is not a sound technical contribution.\n\nMy recommendation: desk reject. The central result is self-conceded, the novelty is thin, and a full review would spend most of its time explaining the constructive gap the author already acknowledges. If the author wants to publish, a position paper that drops the 'solves undecidable problems' framing might find a home.","headline":"Nonconstructive hardcoding and a self-conceded gap sink the central expressiveness claim; the paper is mostly a restatement of prior work.","tokens_in":19342,"tokens_out":2845,"would_cite":false,"duration_ms":28432,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":false},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that evolutionary automata with unbounded generations accept every formal language over a fixed alphabet, placing evolutionary computation beyond Turing machines.","keywords":["Evolutionary Algorithms","Evolutionary Automata","Deep Evolutionary Computing","Expressiveness","Evolution of Evolution","Undecidable Problems","Super-Turing Models of Computation","Terminal Languages"],"falsifier":"Run the Theorem 5.3 construction on the diagonalization language: since the proof assigns one component automaton per word, an effective recipe that outputs those automata would enumerate an undecidable set. Demonstrating that no such recipe can exist, because it would contradict the diagonalization language's non-recursively-enumerable definition, settles the claim as existential rather than algorithmic; demonstrating a recipe would refute the paper's own Remark 5.4.","tokens_in":18318,"feed_emoji":"🧬","tokens_out":9367,"duration_ms":80564,"temperature":0.7,"pith_summary":"The paper sets out to put evolutionary computation on the same analytical footing as classical automata theory by modeling it as an evolutionary automaton: a possibly infinite sequence of automata, each generation handing its population to the next. Its central aim is to prove this model is far more expressive than Turing machines—specifically, that evolutionary finite automata in terminal mode accept every language over a fixed alphabet, decidable or not. The result is meant to show that deep evolutionary computation, evolution over an unbounded number of generations, can in principle handle Turing-machine undecidable problems and matches the expressiveness of interaction machines and oracle machines. A reader should care because the argument recasts what computation can do if evolution is allowed to run forever, although the proof is nonconstructive and the paper acknowledges that limitation.","feed_headline":"Unbounded evolution lets automata accept every language","feed_subtitle":"Unbounded generations let evolution outrun Turing machines in principle, but the construction is nonconstructive.","key_machinery":"The object doing the work is the evolutionary automaton itself—a possibly infinite sequence $E = \\{E[0], E[1], E[2], \\ldots\\}$ of level automata, each applying variation and selection to a population and handing the next generation to the following component. Acceptance in terminal mode means that some component eventually accepts the input word, so the sequence as a whole behaves like an infinite union of the languages of its components. The proof of Theorem 5.3 rests on the per-word finite automaton $A_w$, which recognizes exactly the single string $w$ and passes all other strings to the next generation; this reduces language membership to the question of whether some component recognizes the word. The paper calls the unbounded-generation regime deep evolutionary computation, drawing the analogy to deep neural networks with many layers.","core_discovery":"The central claim is Theorem 5.3: in terminal mode, the class of languages accepted by evolutionary finite automata ($TL(EFA)$) coincides with the class of all languages over the alphabet $\\Sigma$—including languages that are recursively enumerable but not recursive, and languages that are not recursively enumerable at all. For each word $w$ in a target language $L$, the proof builds a finite automaton $A_w$ that accepts exactly $w$ and forwards every other word to the next component; taking the sequence $E = \\{A[t] = A_w : w \\in L\\}$ makes the evolutionary automaton accept the union of these singletons, namely $L$. The paper presents this as showing evolutionary finite automata are more expressive than Turing machines and equally expressive with interaction machines and Turing o-machines. Remark 5.4 concedes the catch: for an undecidable $L$ the components cannot actually be constructed, so the theorem establishes the existence of a recognizing sequence without giving a method to find it.","pith_inferences":["Read as a claim about possible structures rather than algorithms, the theorem is a nonconstructive existence result: without an effective enumeration of $L$, the automaton sequence cannot be built, so the paper does not supply a procedure that solves undecidable problems.","If the component sequence had to be produced by a fixed finite program, the terminal language would be recursively enumerable, which suggests the gap between expressiveness and solvability is exactly the gap between existence and effective construction.","The practical moral is not that infinite evolution literally decides the undecidable, but that increasing the generation horizon is a finite approximation of a limit process, analogous to adding layers to a network."],"forward_implications":["All regular, context-free, and context-sensitive languages over a given alphabet are accepted by evolutionary finite automata, not merely some of them.","Evolutionary finite automata, interaction machines, and Turing o-machines have the same terminal expressiveness; the paper conjectures the same for neural networks, cellular automata, the $\\pi$-calculus, and the $-calculus.","Evolutionary computation with finitely many generations has exactly the power of its component automata; only unbounded generations create the jump beyond Turing machines.","Elitist evolutionary algorithms with complete variation operators converge to global optima as the number of generations goes to infinity, with a proof the paper presents as much simpler than earlier Markov-chain arguments.","If Theorem 5.3 holds, deep evolutionary computation is in principle a super-Turing model, able to express solutions to undecidable problems rather than only approximating them."],"supporting_citations":[{"why":"Defines the evolutionary automata framework that the paper builds on.","marker":"[6]"},{"why":"Earlier result on expressiveness and convergence of evolutionary automata that Theorem 5.3 extends.","marker":"[8]"},{"why":"Initial claim that evolutionary computation can be non-algorithmic and can solve the halting problem.","marker":"[12]"},{"why":"Introduces the evolutionary Turing machine and the theory of evolutionary computation used here.","marker":"[15]"},{"why":"Establishes universality of basic evolutionary finite automata, supporting the expressiveness proof.","marker":"[17]"},{"why":"Supplies the standard automata-theoretic definitions, diagonalization language, and universal language used in comparisons.","marker":"[27]"},{"why":"The theorem that interaction-machine terminal languages equal all languages, which the paper uses as an expressiveness benchmark.","marker":"[39]"},{"why":"Turing's diagonalization argument, used in Remark 5.4 as the contrast showing evolutionary automata are more expressive.","marker":"[42]"}],"fun_headline_variants":["Evolutionary automata can recognize any language in principle","Unbounded evolution gives automata universal language acceptance","Evolutionary automata outmatch Turing machines on language classes","Nonconstructive proof shows evolutionary automata accept all languages","Theoretical edge: evolutionary automata cover every language"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes that for any language $L$, including an undecidable one, one may simply take the sequence of automata $\\{A_w : w \\in L\\}$ even though no effective procedure is given for producing or verifying that sequence.","fun_headline_variants_meta":{"raw":{"variants":["Evolutionary automata can recognize any language in principle","Unbounded evolution gives automata universal language acceptance","Evolutionary automata outmatch Turing machines on language classes","Nonconstructive proof shows evolutionary automata accept all languages","Theoretical edge: evolutionary automata cover every language"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000289,"raw_usage":{"total_tokens":1666,"prompt_tokens":891,"completion_tokens":775,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":507,"completion_tokens_details":{"reasoning_tokens":711}},"tokens_in":507,"tokens_out":775,"duration_ms":7454,"temperature":1.0,"reasoning_tokens":711,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:36:57.882105+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the Theorem 5.3 construction on the diagonalization language: since the proof assigns one component automaton per word, an effective recipe that outputs those automata would enumerate an undecidable set. Demonstrating that no such recipe can exist, because it would contradict the diagonalization language's non-recursively-enumerable definition, settles the claim as existential rather than algorithmic; demonstrating a recipe would refute the paper's own Remark 5.4.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the evolutionary automata framework that the paper builds on."},{"cited_title":"Evolutionary Automata: Expressiveness and Convergence of Evolution- ary Computation, Computer Journal, 55(9), pp.1023-1029, doi: dx.doi.org/10.1093/comjnl/bxr099","cited_arxiv_id":null,"evidence_quote":"Earlier result on expressiveness and convergence of evolutionary automata that Theorem 5.3 extends."},{"cited_title":"On Expressiveness of Evolutionary Computation: Is EC Algorithmic?, Proc","cited_arxiv_id":null,"evidence_quote":"Initial claim that evolutionary computation can be non-algorithmic and can solve the halting problem."},{"cited_title":"Toward a theory of evolutionary computation, BioSystems, v","cited_arxiv_id":null,"evidence_quote":"Introduces the evolutionary Turing machine and the theory of evolutionary computation used here."},{"cited_title":"Evolutionary Automata as Foundation of Evolutionary Computation: Larry Fogel Was Right, Proc","cited_arxiv_id":null,"evidence_quote":"Establishes universality of basic evolutionary finite automata, supporting the expressiveness proof."},{"cited_title":"Introduction to Automata Theory, Languages, and Com- putation, Addison Wesley, Boston/San Francisco/New York","cited_arxiv_id":null,"evidence_quote":"Supplies the standard automata-theoretic definitions, diagonalization language, and universal language used in comparisons."},{"cited_title":"Computational Completeness of Interaction Machines and Turing Machines, Proc","cited_arxiv_id":null,"evidence_quote":"The theorem that interaction-machine terminal languages equal all languages, which the paper uses as an expressiveness benchmark."},{"cited_title":"On Computable Numbers, with an Application to the Entscheidungsproblem, Proc","cited_arxiv_id":null,"evidence_quote":"Turing's diagonalization argument, used in Remark 5.4 as the contrast showing evolutionary automata are more expressive."}],"review_version":1}