{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:18:05Z","timestamp":1725664685472},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540630456"},{"type":"electronic","value":"9783540690658"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1997]]},"DOI":"10.1007\/3-540-63045-7_23","type":"book-chapter","created":{"date-parts":[[2012,2,26]],"date-time":"2012-02-26T22:59:57Z","timestamp":1330297197000},"page":"226-236","source":"Crossref","is-referenced-by-count":3,"title":["Decidability and undecidability of the halting problem on Turing machines, a survey"],"prefix":"10.1007","author":[{"given":"Maurice","family":"Margenstern","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,25]]},"reference":[{"key":"23_CR1","first-page":"77","volume-title":"Papers on Automata and Languages","author":"V. Diekert","year":"1989","unstructured":"Diekert V. and Kudlek M. Small Deterministic Turing Machines, Papers on Automata and Languages, Dep. of Math., Karl Marx Univ. of Economics, Budapest, 1988\u20134, p.77\u201387, (1989)"},{"key":"23_CR2","doi-asserted-by":"crossref","unstructured":"Hermann G.T. The uniform halting problem for generalised one state Turing machines, Proceedings of the Ninth Annual Switching and Automata Theory Symposium, (1968)","DOI":"10.1109\/SWAT.1968.36"},{"key":"23_CR3","first-page":"241","volume":"168\u20132","author":"M. Kudlek","year":"1996","unstructured":"Kudlek M. Small Deterministic Turing Machines, Theoretical Computer Science, 168\u20132, Special issue on Universal Machines and Computations, 241\u2013255, (1996)","journal-title":"Special issue on Universal Machines and Computations"},{"key":"23_CR4","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1007\/3-540-57163-9_32","volume":"710","author":"M. Margenstern","year":"1993","unstructured":"Margenstern M. Turing machines: on the frontier between a decidable halting problem and universality. Lecture Notes in Computer Science, 710, 375\u2013385, in Proceedings of FCT'93, (1993)","journal-title":"Lecture Notes in Computer Science"},{"key":"23_CR5","doi-asserted-by":"crossref","first-page":"386","DOI":"10.1007\/3-540-59175-3_104","volume":"911","author":"M. Margenstern","year":"1995","unstructured":"Margenstern M. Non-erasing Turing machines: a new frontier between a decidable halting problem and universality. Lecture Notes in Computer Science, 911, 386\u2013397, in Proceedings of LATIN'95), (1995)","journal-title":"Lecture Notes in Computer Science"},{"key":"23_CR6","unstructured":"Margenstern M. Results on the halting problem, LMPS'95 International Conference, Florence, August 1995"},{"key":"23_CR7","doi-asserted-by":"crossref","unstructured":"Margenstern M. The laterality problem for non-erasing Turing machines on {0,1} is completely solved. RAIRO, 39p. (1997) (to appear)","DOI":"10.1051\/ita\/1997310201591"},{"issue":"I","key":"23_CR8","first-page":"1395","volume":"320","author":"M. Margenstern","year":"1995","unstructured":"Margenstern M. and Pavlotskaya L. Deux machines de Turing universelles \u00e0 au plus deux instructions gauches. C.R.A.S., Paris, 320, I, 1395\u20131400, (1995)","journal-title":"C.R.A.S., Paris"},{"key":"23_CR9","unstructured":"Margenstern M. and Pavlotska\u00cfa L. Vers une nouvelle approche de l'universalit\u00e9 concernant les machines de Turing, LITP\/IBP research report N\u213495.58 (1995)"},{"key":"23_CR10","volume-title":"Computation: Finite and Infinite Machines","author":"M.L. Minsky","year":"1967","unstructured":"Minsky M.L. Computation: Finite and Infinite Machines. Prentice Hall, Englewood Cliffs, N.J. (1967)"},{"issue":"6","key":"23_CR11","first-page":"899","volume":"13","author":"L.M. Pavlotskaya","year":"1973","unstructured":"Pavlotskaya L.M. Razreshimost' problemy ostanovki dlja nekotorykh klassov mashin T'juringa. Matematicheskie Zametki, 13, (6), 899\u2013909, Ijun' 1973 899\u2013909. (transl. Solvability of the halting problem for certain classes of Turing machines, Notes of the Acad. Sci. USSR, 13 (6) Nov.1973, 537\u2013541)","journal-title":"Matematicheskie Zametki"},{"key":"23_CR12","first-page":"52","volume":"27","author":"L.M. Pavlotskaya","year":"1975","unstructured":"Pavlotskaya L.M. O minimal'nom chisle razlichnykh kodov vershin v grafe universal'noj mashiny T'juringa. Diskretnyj analiz, Sbornik trudov instituta matematiki SO AN SSSR, 27, 52\u201360, (1975) (On the minimal number of distinct codes for the vertices of the graph of a universal Turing machine) (in Russian)","journal-title":"Diskretnyj analiz, Sbornik trudov instituta matematiki SO AN SSSR"},{"key":"23_CR13","unstructured":"Pavlotskaya L.M. Dostatochnye uslovija razreshimosti problemy ostanovki dlja mashin T'juring, Avtomaty i mashiny, 91\u2013118, 1978 (Sufficient conditions for halting problem decidability of Turing machines) (in Russian)"},{"key":"23_CR14","first-page":"257","volume":"168-2","author":"L.M Pavlotskaya","year":"1996","unstructured":"Pavlotskaya L.M, On machines, universal by extensions, Theoretical Computer Science, 168-2, Special issue on Universal Machines and Computations, pp.257\u2013266, (1996)","journal-title":"Special issue on Universal Machines and Computations"},{"issue":"4","key":"23_CR15","doi-asserted-by":"crossref","first-page":"508","DOI":"10.1137\/0208041","volume":"8","author":"L. Priese","year":"1979","unstructured":"Priese L. Towards a precise characterization of the complexity of universal and nonuniversal Turing machines, SIAM Journal of Computation, 8, 4, 508\u2013523, (1979)","journal-title":"SIAM Journal of Computation"},{"key":"23_CR16","first-page":"76","volume":"69","author":"J. Rogozhin","year":"1982","unstructured":"Rogozhin Ju.V. Sem' universal'nykh mashin T'juringa. Matematicheskie Issledovanija, 69, 76\u201390, 1982 (Seven universal Turing machines) (in Russian)","journal-title":"Matematicheskie Issledovanija"},{"key":"23_CR17","first-page":"76","volume":"69","author":"J. Rogozhin","year":"1992","unstructured":"Rogozhin Ju.V. Universal'naja mashina T'juringa s 10 sostojanijami i 3 simvolami. Matematicheskie Issledovanija, 69, 76\u201390, 1992 (A universal Turing machine with 10 states and 3 symbols) (in Russian)","journal-title":"Matematicheskie Issledovanija"},{"key":"23_CR18","first-page":"215","volume":"168-2","author":"J. Rogozhin","year":"1996","unstructured":"Rogozhin Ju.V. Small universal Turing machines, Theoretical Computer Science, 168-2, Special issue on Universal Machines and Computations, 215\u2013240, (1996)","journal-title":"Special issue on Universal Machines and Computations"},{"key":"23_CR19","first-page":"157","volume":"34","author":"C.E. Shannon","year":"1956","unstructured":"Shannon C.E. A universal Turing machine with two internal states. Ann. of Math. Studies, 34, 157\u2013165, (1956)","journal-title":"Ann. of Math. Studies"},{"key":"23_CR20","first-page":"230","volume":"42","author":"A.M. Turing","year":"1936","unstructured":"Turing A.M. On computable real numbers, with an application to the Entscheidungsproblem. Proc. Lond. Math. Soc, ser. 2, 42, 230\u2013265 (1936)","journal-title":"Proc. Lond. Math. Soc, ser. 2"},{"key":"23_CR21","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/BF01343730","volume":"152","author":"H. Wang","year":"1963","unstructured":"Wang H. Tag Systems and Lag Systems, Mat. Annalen, 152, (1963), 65\u201374","journal-title":"Mat. Annalen"}],"container-title":["Lecture Notes in Computer Science","Logical Foundations of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-63045-7_23.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T21:15:14Z","timestamp":1605647714000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-63045-7_23"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1997]]},"ISBN":["9783540630456","9783540690658"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-63045-7_23","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1997]]}}}