RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Forthcoming papers Archive Impact factor Subscription Guidelines for authors License agreement Submit a manuscript Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Mat. Zametki: Year: Volume: Issue: Page: Find

 Mat. Zametki, 2002, Volume 71, Issue 5, Pages 732–741 (Mi mz381)

Turing Machines Connected to the Undecidability of the Halting Problem

L. M. Pavlotskaya

Abstract: The problem of finding a Turing machine with undecidable halting problem whose program contains the smallest number of instructions is well known. Obviously, such a machine must satisfy the following condition: by deleting even a single instruction from its program, we get a machine with decidable halting problem. In this paper, Turing machines with undecidable halting problem satisfying this condition are called connected. We obtain a number of general properties of such machines and deduce their simplest corollaries concerning the minimal machine with undecidable halting problem.

DOI: https://doi.org/10.4213/mzm381

Full text: PDF file (187 kB)
References: PDF file   HTML file

English version:
Mathematical Notes, 2002, 71:5, 667–675

Bibliographic databases:

UDC: 510.53+512.54.05

Citation: L. M. Pavlotskaya, “Turing Machines Connected to the Undecidability of the Halting Problem”, Mat. Zametki, 71:5 (2002), 732–741; Math. Notes, 71:5 (2002), 667–675

Citation in format AMSBIB
\Bibitem{Pav02} \by L.~M.~Pavlotskaya \paper Turing Machines Connected to the Undecidability of the Halting Problem \jour Mat. Zametki \yr 2002 \vol 71 \issue 5 \pages 732--741 \mathnet{http://mi.mathnet.ru/mz381} \crossref{https://doi.org/10.4213/mzm381} \mathscinet{http://www.ams.org/mathscinet-getitem?mr=1936197} \zmath{https://zbmath.org/?q=an:1029.03026} \transl \jour Math. Notes \yr 2002 \vol 71 \issue 5 \pages 667--675 \crossref{https://doi.org/10.1023/A:1015840005656} \isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000176477200009} \scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-0141513942}