TransWikia.com

Does the set ALL_TM contain all Turing Machines?

Computer Science Asked by MKUltra on January 18, 2021

ALL_TM = { TM | A valid TM }

This was a question on my exam.

As my choice of answer I went with yes, since the set of all Turing Machines is countable, ( you can produce a binary string for each and every new Turing Machine ) my take on the answer that yes it does contain all Turing machines. But apparently my answer was wrong so I am curious

why ?

Thanks in advance for anyone’s answer !

One Answer

It turned out that the set of ALL_TM = { | M accepts all strings }, the set wasn't specified on the exam and I have seen it within notes but it was in the formulation that I have stated above so that was a bit confusing !

Anyway the set of ALL_TM does not contain all TM's since it only contains TM's that accept all strings.

Correct answer by MKUltra on January 18, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP