Problem on undecidable problems

[WWCY]

Homework Statement

I need help deciding whether or not the following tasks are undecidable (problems 1c, 1d and 1e).

I have attempted solutions but am very unsure if they are right.

Relevant Equations

Definition of blackbox property: A property P(T) (where T is a Turing machine) is a blackbox property iff P(T) = P(T') for all T,T' such that they halt on the same inputs x and on the inputs they halt, T(x) = T'(x).

Rice's theorem: Any non-trivial blackbox property is undecidable

I should first note that I am not a compsci student, and have not learned the "formal" way of using "Languages" to solve such problems. All I have are the two definitions provided above. Thanks!

1b) This is the Halting problem: Undecidable

1c) I have a feeling that this is decidable, since if you peer into any given Turing machine you'd be able to count the timesteps?

1d) I think this is undecidable; suppose $\exists \ \text{Turing} \ H$ that outputs $1$ if $T,T'$ both return $24$ on the same inputs $x$ and $0$ otherwise. If I design the valid Turings $T,T'$ that look like $\text{function} \ T(x) \rightarrow \ \text{Execute} \ M(x) \rightarrow \ \text{return} \ 24$ for arbitrarily chosen Turing $M$, then $H(T,T') = 1$. However, $H = 1 \ \text{iff} \ T,T'$ both return $24 \ \text{iff}$ both $M,M'$ halt on arbitrary $x$. This means such $H$ can solve the Halting problem and we have a contradiction; there cannot be such $H$.

1e) The property $P(G):=$ "Will this game $G$ with input $x$ have live cells outside a given area" seems to be a blackbox property; Any two games $G$ and $G'$ with the same input $x$ will surely give the same output as the rules are deterministic. This is also non-trivial as $P$ may differ from input to input. So by Rice's theorem it is uncomputable?

Thanks in advance for any assistance

 

[SSequence]

(b) For this the answer is: yes it is not a computable function. However, this is not the same as halting problem. This is problem of determining the totality of a function computed by a given program.

What you want to show is that given the function: $total:\mathbb{N} \rightarrow \{0,1\}$ you can compute the function $halt:\mathbb{N}^2 \rightarrow \{0,1\}$.

$halt(x_1,x_2)=1$ ---- the TM with index $x_1$ halts when given an input $x_2$
$halt(x_1,x_2)=0$ ---- the TM with index $x_1$ doesn't halt when given an input $x_2$

$total(x)=1$ ---- the TM with index $x$ computes a total function
$total(x)=0$ ---- the TM with index $x$ doesn't compute a total function

So suppose you are given two inputs $x_1,x_2 \in \mathbb{N}$ and you want to compute $halt(x_1,x_2)$ using the function $total$ at your disposal. The problem we face is that if we just try to compute $total(x_1)$ that doesn't help us in telling directly whether the given program(with index $x_1$) specifically on $x_2$ or not. For example, suppose our program with index $x_1$ halts on input $x_2$ but loops forever on some other input (say $a$, where $a \neq x_2$). In that case we will get:
$halt(x_1,x_2)=1$
$total(x_1)=0$ (since the program with index $x_1$ doesn't represent a total function)

We want to modify the program with index $x_1$ (in a "computable" way so that the new program has index $f(x_1,x_2)$, where $f:\mathbb{N}^2 \rightarrow \mathbb{N}$ is a total computable function). We want a program [with the index denoted as $f(x_1,x_2)$] so that no matter what input is given to it (say $x$) is given to it, it first modifies it to $x_2$. Then it mimics the behaviour of the program with index $x_1$.
[What it means is that the new program with index $f(x_1,x_2)$ will give the same answer on all inputs. And that answer will equal to the value $halt(x_1,x_2)$. So this new program will either halt on all inputs or loop forever on all inputs.]

What we actually want to do is first compute the function $f$ above and then make the call $total(f(x_1,x_2))$. This will compute the function $halt(x_1,x_2)$ for us. And hence we conclude that $total:\mathbb{N} \rightarrow \{0,1\}$ is not a computable function.

Short: You can just use rice's theorem.

(c) Yes, this is computable. You need the property that there is one TM program which can just take the index of any program and simulate it.I don't know the answer to (e) as I am not familiar how game of life simulates other computational models. For (d), I will make another post.


Edit: Made a small correction in (b). Strictly speaking, I think one should view $f$ as function of two variables rather than one.

 

[SSequence]

(d) Suppose we are given indexes $x_1,x_2$ for two machines and we have to tell whether these machines output $24$ exactly on the same set of inputs or not. Let's call this function $F:\mathbb{N}^2 \rightarrow \{0,1\}$

There would be many ways to approach this. To be honest, I will have to think more carefully about how to apply rice's theorem (it will just be some use of pairing function) because as I see online, it only seems to be stated for properties that relate to functions of one variable.

One easy way to see the above as uncomputable function is simply to observe that we can compute the function $total:\mathbb{N} \rightarrow \{0,1\}$ using this function $F$. Since we already have shown $total$ is not computable, what we actually show is that this function $F$ is not computable.

Consider some program with index $e$ that computes the constant function $24$. That is, this program returns $24$ on all inputs. Now suppose, given an input $x$, we want to compute $total(x)$.

Once again we modify the given program with index $x$ to form a program with new index $f(x)$ [once again $f:\mathbb{N} \rightarrow \mathbb{N}$ being total computable]. What we want to do is that insert a small further logic right at the end where the program with index $x$ halts. This logic is simply: "erase the tape completely and re-write 24 as output".

Observe that, for a given input, the program with index $f(x)$ either doesn't halt and if it does, then it always has 24 as output. So when we make the call $F(f(x),e)$, if you think carefully, this actually gives us the value of $total(x)$.

Hence $F$ can be used to compute $total$ (which isn't a computable function). Therefore $F$ is not a computable function.

 

[WWCY]

This was really helpful, cheers!

 

[willem2]

1e) The property P(G):=P(G):=P(G):= "Will this game GGG with input xxx have live cells outside a given area" seems to be a blackbox property; Any two games GGG and G′G′G' with the same input xxx will surely give the same output as the rules are deterministic. This is also non-trivial as PPP may differ from input to input. So by Rice's theorem it is uncomputable?

With a finite number of cells, the grid will have a finite number of possible states. Any initial configuration will repeat or run off the grid in a finite time, so this is computable.

 

[WWCY]

Hi, thanks for your response

With a finite number of cells, the grid will have a finite number of possible states. Any initial configuration will repeat or run off the grid in a finite time, so this is computable.

In hindsight, this actually seems similar to asking whether or not a Turing machine $T$ with finite input $t$ halts on $t$. From what I know, Rice's theorem doesn't apply to such a situation as it applies only for ideal $T$ that have arbitrary inputs (rather than only finite-length ones) $x$. I seem to recall that such a property is decidable by virtue of the finite state space.

Is this what I got wrong in my application of Rice's theorem in part e)? ie Does Rice's theorem not apply in a game of life with finite-size inputs?

Cheers.

 

[SSequence]

For post#5, perhaps you didn't understand it completely. Here is one way to view it. I will try to explain using analogy with some other situations:
Suppose I gave you a program (in a fixed/easy to understand) programming language. Also, we know that:
(a) there are only five variables used: say $t1$, $t2$, $t3$, $t4$, $t5$. The value of variables is assumed to be non-negative [assume that there is no other "variable-type" other than non-negative integers]. That is: $t1, t2, t3, t4, t5 \geq 0$.
(b) the maximum value any variable can have is $≤100$. What that means is that there is no point in execution of program where we could have $t1=101$ for example (since the max. value was $100$).

One might ask the question: is the halting problem for such any program [that satisfies the above two constraints] decidable? The answer is yes.

To see how suppose we labelled the line numbers in our program as:
(0) -----
(1) -----
...
(n-1) -----

meaning that the program has length equal to $n$ lines. Now we can define the notion of a snapshot as an (ordered) list of values (the length of list is 6):
(value of t1, value of t2, value of t3, value of t4, value of t5, current line-number)

The key points are this:
$(i)$ Once we fix the value of $n$, the number of snapshots are finite.
$(ii)$ From a given snapshot can computation moves to a unique snapshot (rather than two different snapshots for example). That's simply because the computation is deterministic.
[Both these points will also apply to game of life question in (e) too]

For example, let's fix $n=1000$. Assuming that our variables $t1,t2,t3,t4,t5 \geq 0$, we will have total number of possible snapshots as:
$101 \cdot 101 \cdot 101 \cdot 101 \cdot 101 \cdot 1000$
$=(101)^5 \cdot 1000$

So think about it this way: essentially you have a finite state machine of sorts (with a certain start state) and you can only choose one arrow for the next state [also arrows don't have any labels]. Each state can be thought of as a snapshot. Now by pigeonhole principle, there must be a repetition in snapshot at $\leq (101)^5 \cdot 1000$ number of steps.

The repetition in snapshot causes the program to fall in what we can call "snapshot loop". This is a key point, so I hope you can see that why this is true.

============

Whatever I said before also holds to game of life example too (it would be an interesting exercise to put an upper-bound on total number of snapshots). In general, this is why when in a (deterministic) computational model one bounds the memory to a given constant, the (corresponding) halting problem becomes decidable.