Skip to main content
added 1 character in body
Source Link

As we know, that the halting problem of Turing machines is undecidable. givegiven some restriction on $TM$ set of Turing Machines, we get a subclass $TM_s$, halting problem of what subclasses of $TM$ can be decidable?

Does there exist a subclass $TM_{max}$ halting problem of which is decidable such that any decidable subclass $TM_s\subseteq TM_{max}$?

The two questions possibly are too broad, any concrete answer is welcome.

Any reference is welcome

As we know, that the halting problem of Turing machines is undecidable. give some restriction on $TM$ set of Turing Machines, we get a subclass $TM_s$, halting problem of what subclasses of $TM$ can be decidable?

Does there exist a subclass $TM_{max}$ halting problem of which is decidable such that any decidable subclass $TM_s\subseteq TM_{max}$?

The two questions possibly are too broad, any concrete answer is welcome.

Any reference is welcome

As we know, that the halting problem of Turing machines is undecidable. given some restriction on $TM$ set of Turing Machines, we get a subclass $TM_s$, halting problem of what subclasses of $TM$ can be decidable?

Does there exist a subclass $TM_{max}$ halting problem of which is decidable such that any decidable subclass $TM_s\subseteq TM_{max}$?

The two questions possibly are too broad, any concrete answer is welcome.

Any reference is welcome

edited title
Link

Halting problem about any subclass of Turing Machines

added 39 characters in body
Source Link

As we know, that the halting problem of Turing machines is undecidable. give some restriction on $TM$ set of Turing Machines, we get a subclass $TM_s$, halting problem of what subclasses of $TM$ can be decidable?

Does there exist a subclass $TM_{max}$ suchhalting problem of which is decidable such that any decidable subclass $TM_s\subseteq TM_{max}$?

The two questions possibly are too broad, any concrete answer is welcome.

Any reference is welcome

As we know, that the halting problem of Turing machines is undecidable. give some restriction on $TM$ set of Turing Machines, we get a subclass $TM_s$, what subclasses of $TM$ can be decidable?

Does there exist a subclass $TM_{max}$ such that any decidable subclass $TM_s\subseteq TM_{max}$?

The two questions possibly are too broad, any concrete answer is welcome.

Any reference is welcome

As we know, that the halting problem of Turing machines is undecidable. give some restriction on $TM$ set of Turing Machines, we get a subclass $TM_s$, halting problem of what subclasses of $TM$ can be decidable?

Does there exist a subclass $TM_{max}$ halting problem of which is decidable such that any decidable subclass $TM_s\subseteq TM_{max}$?

The two questions possibly are too broad, any concrete answer is welcome.

Any reference is welcome

Source Link
Loading