0
$\begingroup$

Suppose I have a universal Turing Machine (UTM) which accepts some input in binary. Is there a computational problem such that the answer to the problem is YES (accepting) for exactly one input (and hence NO for all others), but determining which input is the accepting one is undecidable? Or is there a fundamental reason this cannot happen? Or is determining if this problem exists undecidable?

I assume this is equivalent to asking: is there a property of TMs such that this property is true for exactly one TM and not true for all others such that determining which TM this is true for is undecidable?

Improve this question
$\endgroup$
3
  • $\begingroup$ What do you mean by input? If you mean a particular formal language then the answer is yes...if you mean a particular instance of a formal language then the TM will either accept all inputs (all the membership in that language) or reject/loop forever. $\endgroup$
    – Yamar69
    Jun 23, 2019 at 11:33
  • $\begingroup$ I think I mean the following: I have UTM. I give it a rational number as input. The UTM interprets this input in some way (not specified) and then runs on it.I'm then asking about a particular property of the TM (e.g. does the UTM halt?). I'm then asking, is there a property such that this property is true for exactly one input, and false for all others. (Does that make any sense?). $\endgroup$
    – user138901
    Jun 23, 2019 at 12:20
  • $\begingroup$ There might be such a property. For example, let $M_1$, $M_2$, ... be a list of all Turing machines over binary input symbols $\{0,1\}$ and tape symbols $\{0,1, \sqcap\}$. It might be undecidable to determine the first TM whose halting problem is undecidable. The halting problem for a particular TM $T$ is to determine the membership of $L_T :=\{w\mid T\text{ halts on }w\}$. $\endgroup$
    – John L.
    Jun 23, 2019 at 18:49

2 Answers 2

Reset to default
0
$\begingroup$

For every Turing machine over some language L, there is a set of words that it will halt and accept on and a set of words it will halt and reject on, if it does halt.

If $|L| = 1 $ then the Turing machine will accept on exactly one input.

Given an arbitrary M and some input, we cannot decide whether the program will halt; halting problem. However, since M is not arbitrary, it’s fixed,this is not the Halting problem. I believe an algorithm would only need to check if the input is equal to the first element in L.

Improve this answer
$\endgroup$
3
  • $\begingroup$ So essentially there is no such problem because any finite language is decidable? $\endgroup$
    – user138901
    Jun 23, 2019 at 12:22
  • $\begingroup$ @user138901 yes, for the problem you gave, I could just hard-wire the input I know it will always accept, then reject on anything that is not that input. I assumed that by Language, we mean the set of all solutions to a problem, or the naturally occurring language from some problem $\endgroup$
    – user106386
    Jun 23, 2019 at 12:43
  • 2
    $\begingroup$ Gah, this seems obvious now. Thanks for the help. $\endgroup$
    – user138901
    Jun 23, 2019 at 12:45
0
$\begingroup$

We can enumerate all possible inputs, giving them numbers 1, 2, 3, 4, ...

We can then write a program that systematically checks if one of the first n inputs is accepted in n steps, for n = 1, 2, 3 etc. This will in finite time find the input that halts.

I wasn't qute sure if I would call the approach of user679128 to be "cheating" since the question was about a situation where the only element of $L$ was presumably hard or impossible to find. So we see it is easy (but likely very time consuming) to find, so the algorithm of user679128 can then easily be implemented in practice.

Where my approach doesn't work is a situation like "assume the answer is YES for a finite number of instances", unless you give me the exact number of instances. Even "assume the answer is YES for either one or two instances" doesn't allow me to find all instances where the answer is YES. IF there are two instances I will find them eventually, but if there is only one instance I wouldn't know when to stop searching.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.