{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,6]],"date-time":"2022-12-06T05:27:57Z","timestamp":1670304477250},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1997,3]]},"abstract":"We show that a Turing machine with two single-head one-dimensional tapes cannot recognize the set.<\/jats:p>","DOI":"10.1145\/256303.256308","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:25:57Z","timestamp":1027769157000},"page":"237-256","source":"Crossref","is-referenced-by-count":6,"title":["Two heads are better than two tapes"],"prefix":"10.1145","volume":"44","author":[{"given":"Tao","family":"Jiang","sequence":"first","affiliation":[{"name":"McMaster University, Hamilton, Ontario, Canada"}]},{"given":"Joel I.","family":"Seiferas","sequence":"additional","affiliation":[{"name":"University of Rochester, Rochester, New York"}]},{"given":"Paul M. B.","family":"Vit\u00e1nyi","sequence":"additional","affiliation":[{"name":"CWI and Universiteit van Amsterdam, Amsterdam, The Netherlands"}]}],"member":"320","published-online":{"date-parts":[[1997,3]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"75","volume-title":"Complexity of Computation (SIAM-AMS Proceedings 7) R. M. Karp. ed. American Mathematical Society, Providence, R. I.","author":"AANDERAA S.","year":"1974","unstructured":"AANDERAA , S. 0. 1974 . 1974. On k-tape versus (k - 1)-tape real time computation . In Complexity of Computation (SIAM-AMS Proceedings 7) R. M. Karp. ed. American Mathematical Society, Providence, R. I. , pp. 75 - 96 . AANDERAA, S. 0. 1974. 1974. On k-tape versus (k - 1)-tape real time computation. In Complexity of Computation (SIAM-AMS Proceedings 7) R. M. Karp. ed. American Mathematical Society, Providence, R. I., pp. 75-96."},{"key":"e_1_2_1_2_1","first-page":"475","article-title":"Real-time and complexity problems in automata theory","volume":"1","author":"BE V#.","year":"1965","unstructured":"BE # V#. #,, J. 1965 . Real-time and complexity problems in automata theory . Kyberntika 1 , 6, 475 - 497 . BE#V#.#,, J. 1965. Real-time and complexity problems in automata theory. Kyberntika 1, 6, 475- 497.","journal-title":"Kyberntika"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008304.1008308"},{"key":"e_1_2_1_4_1","first-page":"3","article-title":"Coding strings by pairs of strings","volume":"6","author":"CHUNG F. R.","year":"1985","unstructured":"CHUNG , F. R. K., TARJAN , R. E. , PAUL , W. J. , AND REISCHUK , R. 1985 . Coding strings by pairs of strings . SIAM J. Disc. Math. 6 , 3 (July), 445-461. CHUNG, F. R. K., TARJAN, R. E., PAUL, W. J., AND REISCHUK, R. 1985. Coding strings by pairs of strings. SIAM J. Disc. Math. 6, 3 (July), 445-461.","journal-title":"SIAM J. Disc. Math."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(84)80019-4"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/321724.321726"},{"key":"e_1_2_1_7_1","first-page":"3","article-title":"Imbedding theorems for Turing machines of different dimensions and Kolmogorov's algorithms. Soy","volume":"18","author":"GRIGOR V, D","year":"1977","unstructured":"GRIGOR m V, D . Yu. 1977 . Imbedding theorems for Turing machines of different dimensions and Kolmogorov's algorithms. Soy . Math. 18 , 3 (May-June), 588-592. GRIGORmV, D. Yu. 1977. Imbedding theorems for Turing machines of different dimensions and Kolmogorov's algorithms. Soy. Math. 18, 3 (May-June), 588-592.","journal-title":"Math."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1090\/S0002-9947-1965-0170805-7","article-title":"On the computational complexity of algorithms","volume":"117","author":"HARTMANIS J.","year":"1965","unstructured":"HARTMANIS , J. , AND STEARNS , R.E. 1965 . On the computational complexity of algorithms . Trans. Am. Math. Soc. 117 , 5 (May), 285-306. HARTMANIS, J., AND STEARNS, R.E. 1965. On the computational complexity of algorithms. Trans. Am. Math. Soc. 117, 5 (May), 285-306.","journal-title":"Trans. Am. Math. Soc."},{"key":"e_1_2_1_9_1","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1109\/PGEC.1966.264374","article-title":"On-line Turing machine computations","volume":"1","author":"HENNIE F.C.","year":"1966","unstructured":"HENNIE , F.C. 1966 . On-line Turing machine computations . IEEE Trans. Elect. Comput. EC-15 , 1 ( Feb. ), 35 - 44 . HENNIE, F.C. 1966. On-line Turing machine computations. IEEE Trans. Elect. Comput. EC-15, 1 (Feb.), 35-44.","journal-title":"IEEE Trans. Elect. Comput. EC-15"},{"key":"e_1_2_1_10_1","first-page":"1","article-title":"Three approaches to the quantitative definition of information","volume":"1","author":"KOLMOGOROV A.N.","year":"1965","unstructured":"KOLMOGOROV , A.N. 1965 . Three approaches to the quantitative definition of information . Prob. Inf. Transm. 1 , 1 (Jan.-Mar.), 1-7. KOLMOGOROV, A.N. 1965. Three approaches to the quantitative definition of information. Prob. Inf. Transm. 1, 1 (Jan.-Mar.), 1-7.","journal-title":"Prob. Inf. Transm."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/322234.322246"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221042"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(88)90003-X"},{"key":"e_1_2_1_14_1","volume-title":"An Introduction to Kolmogorov Complexity and Its Applications","author":"LI M.","unstructured":"LI , M. , AND VITANYI , P. M. B. 1993. An Introduction to Kolmogorov Complexity and Its Applications . Springer-Verlag , New York . LI, M., AND VITANYI, P. M.B. 1993. An Introduction to Kolmogorov Complexity and Its Applications. Springer-Verlag, New York."},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1090\/S0002-9947-1985-0808746-4","article-title":"Combinatorial lower bound arguments for deterministic and nondeterministic Turing machines","volume":"292","author":"MAASS W.","year":"1985","unstructured":"MAASS , W. 1985 . Combinatorial lower bound arguments for deterministic and nondeterministic Turing machines . Trans. Am. Math. Soc. 292 , 2 (Dec.), 675-693. MAASS, W. 1985. Combinatorial lower bound arguments for deterministic and nondeterministic Turing machines. Trans. Am. Math. Soc. 292, 2 (Dec.), 675-693.","journal-title":"Trans. Am. Math. Soc."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01275490"},{"key":"e_1_2_1_17_1","volume-title":"An optimal time bound for a one tape on-line Turing machine computation. Unpublished manuscript. (Earlier version cited in MEYER EY AL","author":"MEYER A.R.","year":"1967","unstructured":"MEYER , A.R. 1971. An optimal time bound for a one tape on-line Turing machine computation. Unpublished manuscript. (Earlier version cited in MEYER EY AL . 1967 .) MEYER, A.R. 1971. An optimal time bound for a one tape on-line Turing machine computation. Unpublished manuscript. (Earlier version cited in MEYER EY AL. 1967.)"},{"key":"e_1_2_1_18_1","first-page":"117","volume-title":"IEEE Conference Record of 1967 8th Annual Symposium on Switching and Automata Theory. IEEE Computer Society, Long Beach, Calif.","author":"MEYER A. R.","year":"1967","unstructured":"MEYER , A. R. , ROSENBERG , A. L. , AND FISCHER , P. C. 1967 . Turing machines with several read-write heads, preliminary report . In IEEE Conference Record of 1967 8th Annual Symposium on Switching and Automata Theory. IEEE Computer Society, Long Beach, Calif. , pp. 117 - 127 . MEYER, A. R., ROSENBERG, A. L., AND FISCHER, P. C. 1967. Turing machines with several read-write heads, preliminary report. In IEEE Conference Record of 1967 8th Annual Symposium on Switching and Automata Theory. IEEE Computer Society, Long Beach, Calif., pp. 117-127."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90005-3"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0019-9958(82)91055-5","article-title":"On-line simulation of k + 1 tapes by k tapes requires nonlinear time","volume":"53","author":"PAUL W.J.","year":"1982","unstructured":"PAUL , W.J. 1982 . On-line simulation of k + 1 tapes by k tapes requires nonlinear time . Inf. Cont. 53 , 1 - 2 (Apr.-May), 1-8. PAUL, W.J. 1982. On-line simulation of k + 1 tapes by k tapes requires nonlinear time. Inf. Cont. 53, 1-2 (Apr.-May), 1-8.","journal-title":"Inf. Cont."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0304-3975(83)90063-4","article-title":"On heads versus tapes","volume":"28","author":"PAUL W.J.","year":"1984","unstructured":"PAUL , W.J. 1984 . On heads versus tapes . Theoret. Comput. Sci. 28 , 1 - 2 (Jan.), 1-12. PAUL, W.J. 1984. On heads versus tapes. Theoret. Comput. Sci. 28, 1-2 (Jan.), 1-12.","journal-title":"Theoret. Comput. Sci."},{"key":"e_1_2_1_22_1","first-page":"2","article-title":"An information-theoretic approach to time bounds for on-line computation","volume":"23","author":"PAUL W. J.","year":"1981","unstructured":"PAUL , W. J. , SEIFERAS , J. I. , AND SIMON , J. 1981 . An information-theoretic approach to time bounds for on-line computation . J. Comput. Syst. Sci. 23 , 2 (Oct.), 108-126. PAUL, W. J., SEIFERAS, J. I., AND SIMON, J. 1981. An information-theoretic approach to time bounds for on-line computation. J. Comput. Syst. Sci. 23, 2 (Oct.), 108-126.","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_23_1","first-page":"4","article-title":"Real time computation","volume":"1","author":"RABIN M.O.","year":"1963","unstructured":"RABIN , M.O. 1963 . Real time computation . Is. J. Math. 1 , 4 (Dec.), 203-211. RABIN, M.O. 1963. Real time computation. Is. J. Math. 1, 4 (Dec.), 203-211.","journal-title":"Is. J. Math."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90037-0"},{"issue":"3","key":"e_1_2_1_25_1","first-page":"309","article-title":"k-Band-Simulation von k-Kopf-Turing-Maschinen","volume":"6","author":"STOI","year":"1970","unstructured":"STOI 3, H.- J. 1970 . k-Band-Simulation von k-Kopf-Turing-Maschinen . Computing 6 , 3 , 309 - 317 (in German). STOI3, H.-J. 1970. k-Band-Simulation von k-Kopf-Turing-Maschinen. Computing 6, 3, 309-317 (in German).","journal-title":"Computing"},{"key":"e_1_2_1_26_1","first-page":"6","article-title":"\/1973. Certain estimates of the time of computation on Turing machines with an input","volume":"6","author":"VAL V, K","year":"1970","unstructured":"VAL m V, K . 1970 \/1973. Certain estimates of the time of computation on Turing machines with an input . Cybernetics 6 , 6 (June 1973), 734-741 (translated from Russian, published in Kibernetika 6, 6 (Nov.-Dec. 1970), 26-32). VALmV, K. 1970\/1973. Certain estimates of the time of computation on Turing machines with an input. Cybernetics 6, 6 (June 1973), 734-741 (translated from Russian, published in Kibernetika 6, 6 (Nov.-Dec. 1970), 26-32).","journal-title":"Cybernetics"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1016\/0022-0000(84)90001-1","article-title":"On two-tape real-time computation and queues","volume":"29","author":"VITANYI P. M.","year":"1984","unstructured":"VITANYI , P. M. B. 1984 . On two-tape real-time computation and queues . J. Comput. Syst. Sci. 29 , 3 (Dec.), 303-311. VITANYI, P. M.B. 1984. On two-tape real-time computation and queues. J. Comput. Syst. Sci. 29, 3 (Dec.), 303-311.","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1070\/RM1970v025n06ABEH001269","article-title":"The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms","volume":"25","author":"ZVONKIN A. K.","year":"1970","unstructured":"ZVONKIN , A. K. , AND LEVIN , g. A. 1970 . The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms . Russ. Math. Surv. 25 , 6 (Nov.-Dec.), 83-124. ZVONKIN, A. K., AND LEVIN, g.A. 1970. The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russ. Math. Surv. 25, 6 (Nov.-Dec.), 83-124.","journal-title":"Russ. Math. Surv."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/256303.256308","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,5]],"date-time":"2022-12-05T19:26:33Z","timestamp":1670268393000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/256303.256308"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997,3]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[1997,3]]}},"alternative-id":["10.1145\/256303.256308"],"URL":"http:\/\/dx.doi.org\/10.1145\/256303.256308","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[1997,3]]}}}