{"id":"W2168431435","doi":"10.1016/j.tcs.2009.08.031","title":"Theory of one-tape linear-time Turing machines","year":2009,"lang":"en","type":"article","venue":"Theoretical Computer Science","topic":"Quantum Computing Algorithms and Architecture","field":"Computer Science","cited_by":62,"is_retracted":false,"has_abstract":false,"ca_institutions":"University of Ottawa","funders":"","keywords":"Time hierarchy theorem; Turing machine; Probabilistic Turing machine; Non-deterministic Turing machine; DTIME; NSPACE; Super-recursive algorithm; Computer science; Nondeterministic algorithm; Time complexity; Universal Turing machine; NP; Description number; Theoretical computer science; PSPACE; Complexity class; Algorithm; Computational complexity theory; Computation","routes":{"ca_aff":true,"ca_fund":false,"ca_venue":false,"about_ca":false,"invisible_to_affiliation_only":false},"retraction":null,"screen":null,"direct_labels":[],"prediction":{"model_version":"codex-gemma-dda1882f352a","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.001954841,0.0002339474,0.0003355728,0.0002479138,0.000343899,0.0001984322,0.003227566,0.00005720599,0.0000344902],"category_scores_gemma":[0.0001152713,0.000182592,0.00011747,0.001220546,0.001575627,0.0003610361,0.0008812558,0.0002957798,0.00005036166],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.00002225688,"about_ca_system_score_gemma":0.00009962184,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.00000110958,"about_ca_topic_score_gemma":3.436932e-8,"domain_scores_codex":[0.9973139,0.0001674891,0.0003791781,0.0007406356,0.0007758592,0.000622956],"domain_scores_gemma":[0.9980854,0.0003828813,0.0001201856,0.0009899217,0.0001729353,0.0002486971],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"simulation_or_modeling","study_design_scores_codex":[0.000007636224,0.00008128109,0.000007732903,0.000004846202,0.00000347216,0.000006597757,0.0003367828,0.001851853,0.003313643,0.7334092,0.000006153233,0.2609708],"study_design_scores_gemma":[0.0001277518,0.0002925239,0.00153165,0.0000479834,0.000003371744,0.00003176261,7.441423e-7,0.6660359,0.007536235,0.324204,0.00001558677,0.0001724732],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":null,"genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.1302889,0.00004959446,0.8656783,0.001137951,0.0003111229,0.0001087137,0.000001102172,0.0002786822,0.002145689],"genre_scores_gemma":[0.6878503,0.000001473547,0.3114457,0.0004943269,0.0001899786,5.722516e-7,3.162231e-7,0.000005274769,0.00001203147],"genre_candidate":"methods","genre_consensus":null,"teacher_disagreement_score":0.664184,"threshold_uncertainty_score":0.7445885,"prediction_status":"machine_predicted_unvalidated"},"machine_scores":{"provisional":true,"baseline":true,"maturity_gate_passed":false,"score_opus":0.007599579880102563,"score_gpt":0.2347399143056652,"score_spread":0.2271403344255626,"validation_status":"score_only:v0-immature-baseline","note":"Baseline scores from an immature model (maturity gate not passed). Scores rank; they never assert a category."}}