{"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":"metacan-v3-hybrid-931329e0061c","candidate_categories":[],"consensus_categories":[],"category_scores_codex":[0.001136252,0.0008066795,0.001447409,0.001277268,0.002680531,0.0041567,0.003273267,0.002582411,0.01254018],"category_scores_gemma":[0.003763836,0.000685333,0.001258351,0.001508987,0.005291444,0.007821811,0.00234087,0.004690436,0.002257043],"about_ca_system_candidate":false,"about_ca_system_consensus":false,"about_ca_system_score_codex":0.002856491,"about_ca_system_score_gemma":0.00220774,"about_ca_topic_candidate":false,"about_ca_topic_consensus":false,"about_ca_topic_score_codex":0.001264712,"about_ca_topic_score_gemma":0.0009311443,"domain_scores_codex":[0.998628,0.000370457,0.00007572016,0.0001959699,0.0004315518,0.0002982879],"domain_scores_gemma":[0.9975429,0.001306178,0.0001325015,0.00046832,0.0003374595,0.0002127095],"domain_codex":null,"domain_gemma":null,"domain_candidate":null,"domain_consensus":null,"study_design_codex":"theoretical_or_conceptual","study_design_gemma":"theoretical_or_conceptual","study_design_scores_codex":[0.000007092814,0.000006205685,0.00001721475,0.00002473412,0.000001996334,0.00001361187,0.00004280465,0.0008656991,0.00009270269,0.9969898,0.0008557118,0.001082373],"study_design_scores_gemma":[0.000007606395,0.00000454492,0.00001589271,0.000007942545,0.0000029995,0.00001866537,0.00001274984,0.004590824,0.000157039,0.9935728,0.001603346,0.000005547905],"study_design_candidate":"theoretical_or_conceptual","study_design_consensus":"theoretical_or_conceptual","genre_codex":"methods","genre_gemma":"empirical","genre_scores_codex":[0.08120152,0.005200962,0.5976272,0.01501475,0.001172669,0.0001961595,0.001465649,0.001398703,0.2967223],"genre_scores_gemma":[0.852025,0.00334691,0.0807887,0.001854956,0.001020054,0.0004350707,0.0009290754,0.0002985333,0.05930163],"genre_candidate":"empirical","genre_consensus":null,"teacher_disagreement_score":0.01254018,"threshold_uncertainty_score":0.04195112,"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."}}