7
Yes, with such a powerful oracle, the halting problem can be solved.
To be clearer, given an arbitrary Turing machine, the oracle will tell the set of words accepted by that Turing machine is finite or not.
Suppose we are given a Turing machine $M$ and an input $x$. Let us construct Turing machine $M'$ such that on all inputs, $M'$ will simulate $M$ running ...
7
I'm afraid that your logic doesn't make sense, since you can't implement Step 1. In order to implement it, you'll have to run $M$ and see if it every halts, but this is impossible, since it's the halting problem.
Nevertheless, the problem is decidable. The details of this argument depend on the exact Turing machine model, but in order to illustrate the basic ...
3
The problem is decidable. You can enumerate the (finitely many) programs that use at most $b$ bytes.
For each such candidate program $P$, you can check whether $P$ is valid program (for any reasonable representation) and execute it for up to $t$ time steps. Eventually you either find a program that prints $s$ (and accept) or you run out of programs (and ...
2
The intent of this assignment seems to be to demonstrate that allowing Turing Machines to treat the tape as infinite in both directions will not increase the computational power of the Turing Machine; in other words, that for any unbounded-tape TM, there exists an equivalent classical TM. This means you can't just "reject if we go too far to the left&...
2
The languages are not the same.
In the first one, $w$ is a part of the input.
In the second one, $w$ is fixed beforehand, and the language has to depend on what you fix it to be.
2
Modern computers are not more powerful than a TM.
The meaning/definition of "mechanical means" is not "a TM"; "mechanical means" refers to any step-by-step process that can be carried out in the real, physical world. For instance, it would include mechnical devices, electronic devices, a human following a procedure "...
2
I claim that $L$ is decidable and I will construct a Turing machine to decide $L$.
Let $M$="on input $\langle M' \rangle$
$\quad ACCEPT$ "
Why does $M$ decide $L$? $M$ takes a description of a Turing machine as input and accepts, that is $L(M)=\{ \langle T \rangle \mid T \text{ is a Turing machine}\}$. If the input is not a description of a Turing ...
1
An LBA is limited to working only on the space defined by the input. That means it won't ever move right on reading a blank space (if your model doesn't allow writing blank, only a fake blank, that is). That is easy to check by looking at the transitions of the TM.
To check if the language is accepted by an LBA is undecidable by Rice's theorem.
1
I think since the input word is delimited by special symbols, which the machine cannot move past, the language accepted by such a device should be finite. We know that all finite languages are regular, and regular languages are decidable by a TM. Does it make sense for answering the question?
You can easily simulate any DFA in your model, and so your model ...
1
The Turing machine M is running the Turing machine E as its subroutine. In the other words, you can think of E's printer tape as another tape for Turing machine M. Although we don't know what is going on E, E's computation is part of (inside) M's computation. And of course, as nir shahr said in the comment, comparing is part of M's computation too.
I drew ...
1
The question is given you have an oracle machine/black box for HPC can you decide if <M,w1,w2,w3> is in LOOP.
See the wikipedia page on that: https://en.m.wikipedia.org/wiki/Reduction_(recursion_theory)#Turing_reducibility
The proof is very straightforward as you already know.
1
If $E_{DFA}$ with input $C$ accepts, then $C = L(M) \cap B = \emptyset$.
In other words, no word containing an odd number of 1s is also in $L(M)$.
Then, by definition of $A$ you should accept.
Conversely, if $E_{DFA}$ with input $C$ rejects, then $C = L(M) \cap B \neq \emptyset$.
That is, there is some word $w \in L(M)$ such that $w$ contains an odd number ...
1
While a specific program could be self-delimiting, in this context what we usually mean is a self-delimiting encoding of programs. An encoding of programs is self-delimiting if it forms a prefix code, that is, no program is a prefix of another program. Intuitively, programs are self-delimiting, so there is no ambiguity in where a program ends.
Why do we care?...
1
The language $S = S_1 \circ S_2$ (I'm assuming that was the intended notation) is in NP if $S_1,S_2$ are in NP. Indeed, given verifiers for $S_1,S_2$, we can construct a non-deterministic verifier for $S$ as follows:
Given an input $x \in \{0,1\}^*$, guess a decomposition $x = x_1 \ldots x_n$ for even $n$, and use the verifiers for $S_1,S_2$ to verify that $...
1
You want to show that this modified Turing machine is equivalent to the standard definition of a Turing machine, that is for every modified Turing machine $T'$ there exists a standard Turing machine $T$ such that $L(T')=L(T)$, and vice versa.
It is easy to show that for every standard Turing machine $T$ there is a modified Turing machine which accepts $L(T)$,...
1
Let $L$ be a decidable language and let $M$ be a decider for $L$. Since $M$ decides $L$, $M$ always halts and accepts if its input is in $L$ and rejects if its input is not in $L$.
We know that string reversal can be performed by a Turing machine. Let's construct a Turing machine to decide if a word is in $L^r=\{w=w_0w_1...w_n \mid w^r=w_nw_{n-1}...w_0\in L\}...
1
Suppose that you have a Turing machine $M$ that accepts a language $L$.
Construct a new Turing machine which, on input $x$, reverses its input and then passes control to $M$. The new Turing machine accepts the reverse of $L$.
Only top voted, non community-wiki answers of a minimum length are eligible
