Transforming multi-tape Turing machines to equivalent single-tape Turing machines

We know that multi-tape Turing machines have the same computational power as single-tape ones. So every $ k$ -tape Turing machine has an equivalent single-tape Turing machine.

About the computability and complexity analysis of such a transformation:

Is there a computable function that receives as input an arbitrary multi-tape Turing machine and returns an equivalent single-tape Turing machine in polynomial time and polynomial space?

How to prove the language of all Turing Machines that accept an undecidable language is undecidable?

I want to prove that $ L=\{\langle M \rangle |L(M)\text{ is undecidable}\}$ is undecidable

I am not sure about this. This is my try :

Suppose L is decidable. Let $ E$ be the decider from $ L$ . Let $ A$ be a TM which is recognizing $ A_{TM}$ . Let $ S$ be a TM which works on input $ \langle M,w \rangle$ in the following way:

  1. Construct a TM $ N$ which works on Input $ x$ as follows: Run $ M$ on $ w$ . If $ M$ $ accepts$ run $ A$ on $ x$ and accept $ x$ if $ A$ accepts.(In this case is $ L(N)=A_{TM}$ ). If $ M$ $ rejects$ $ w$ , $ accept$ $ x$ .(In this case is $ L(N)=\Sigma^*$ )
  2. Run $ E$ on $ N$ and accept if N accepts. Otherwise reject

I am not sure if my reduction is the right way or not. Maybe someone can help to finish the reduction 🙂

Relations between deciding languages and computing functions in advice machines

I’m trying to understand implications of translating between functions and languages for P/Poly complexity. I’m not sure whether the following all makes sense. Giving it my best shot given my current understanding of the concepts. (I have a project in which I want to discuss Hava Siegelmann’s analog recurrent neural nets, which recognize languages in P/Poly, but I’d like to understand and be able to explain to others implications this has for computing functions.)

Suppose I want to use an advice Turing $ T_1$ machine to calculate a function from binary strings to binary strings $ f: {0,1}* \rightarrow {0,1}*$ . $ T_1$ will be a machine that can compute $ f$ in polynomial time given advice that is polynomial-size on the length of arguments $ s$ to $ f$ , i.e. $ f$ is in P/Poly. (Can I say this? I have seen P/Poly defined only for languages, but not for functions with arbitrary (natural number) values.)

Next suppose I want to treat $ f$ as defining a language $ L(f)$ , by encoding its arguments and corresponding values into strings, where $ L(f) = \{\langle s,f(s)\rangle\}$ and $ \langle\cdot,\cdot\rangle$ encodes $ s$ and $ f(s)$ into a single string.

For an advice machine $ T_2$ that decides this language, the inputs are of length $ n = |\langle s,f(s)\rangle|$ , so the relevant advice for such an input will be the advice for $ n$ .


Question 1: If $ T_1$ can return the result $ f(s)$ in polynomial time, must there be a machine $ T_2$ that decides $ \{\langle s,f(s)\rangle\}$ in polynomial time? I think the answer is yes. $ T_2$ can extract $ s$ from $ \{\langle s,f(s)\rangle\}$ , and then use $ T_1$ to calculate $ f(s)$ , and then encode $ s$ with $ f(s)$ and compare it with the original encoded string. Is that correct?


Question 2 (my real question): If we are given a machine $ T_2$ that can decide $ \{\langle s,f(s)\rangle\}$ in polynomial time, must there be a way to embed $ T_2$ in a machine $ T_3$ so that $ T_3$ can return $ f(s)$ in polynomial time?

I suppose that if $ T_2$ must include $ T_1$ , then the answer is of course yes. $ T_3$ just uses the capabilities of $ T_1$ embedded in $ T_2$ to calculate $ f(s)$ . But what if $ T_2$ decides $ L(f)$ some other way? Is that possible?

If we are given $ s$ , we know its length, but not the length of $ f(s)$ . So in order to use $ T_2$ to find $ f(s)$ , it seems there must be a sequential search through all strings $ s_f = \{\langle s,r\rangle\}$ for arbitrary $ r$ . (I’m assuming that $ f(s)$ is unbounded, but that $ f$ has a value for every $ s$ . So the search can take an arbitrary length of time, but $ f(s)$ will ultimately be found.)

One thought I have is that the search for a string $ s_f$ that encodes $ s$ with $ f(s)$ has time complexity that depends on the length of the result $ f(s)$ (plus $ |s|$ , but that would be swamped when $ f(s)$ is long).

So now the time complexity does not have to do with the length of the input, but only the length of $ f(s)$ . Maybe $ L(f)$ is in P/Poly if $ f$ is in P? (Still confused here.)

Thinking about these questions in terms of Boolean circuits has not helped.

Intuition for Church-Turing thesis for Turing machines

I can very clearly see "why" mu-recursion is a universal model of computation, i.e. why the Church-Turing thesis — that any physically computable algorithm can be executed with mu-recursion — holds for mu-recursion. It reflects exactly the type of algorithms that I can carry out with my own brain.

I cannot see an analogous intuition for understanding why the Turing machine can execute any physically computable algorithm — i.e. how did Turing "see" that the Turing machine was a good definition to use? Is there a good way to "imagine" the algorithms I perform in terms of the Turing machine, as opposed to general recursion as I am used to?

Scheduling jobs online on 3 identical machines – a lower bound of 5/3

Consider the Online Scheduling Problem with $ 3$ identical machines. Jobs, with arbitrary size, arrive online one after another and need to be scheduled on one of the $ 3$ machines without ever moving them again.

How can I show, that there can’t be any deterministic Online-Algorithm which achieves a competitive ratio of $ c<\frac{5}{3}$ .

This should be solved by just giving some instance $ \sigma$ and arguing that no det. algorithm can do better. Same can easily be done for $ 2$ machines and $ c<\frac{3}{2}$ . Sadly I can’t find any solution to this (more or less) textbook answer.

Why is the Greedy Algorithm for Online Scheduling on uniform machines NOT competitive?

Consider the Online Scheduling Problem with m machines and different speeds.

Each instance $ \sigma$ consists of a sequence of jobs with different sizes $ j_i\in\mathbb{R^+}$ . At each step in time any algorithm gets to know the one new job of $ \sigma$ which needs to be assigned to one machine. The goal is to minimize the makespan (by the end of the online sequence \sigma$ ).

I want to find an instance such that the Greedy Algorithm, which assigns each new job to the machine which finishes it first, is only $ \Theta(\log m)$ -competitive.

Any ideas? I can’t find any articles regarding my problem.

Describe this Turing machines

I need to describe a Turing machine that it can be multitape.

$ M = (Q,Σ,Γ,δ,q_0,q_a,q_r)$ .

Who decide that language.

$ L=\{\#uqv\#u’q’v’\#:u,v,u’v’∈(Γ\setminus\{\sqcup\}^*,q,q’∈ Q$ and$ (u,q,v) \Rightarrow (u’,q’,v’)\}$ according to M.

on alphabet.

$ \Sigma’=Q\cup(Γ\setminus\{\sqcup\})\cup\{\#\}$

But I not sure to understand the language and the alphabet $ \Sigma’$ , do you have exemple that could help me to understand. Thanks

How to conceive a Turing machine that is the intersection of the languages of two Turing machines?

We have $ M = (Q,Σ,Γ,δ,q_0,q_a,q_r) $ and $ M′= (Q′, Σ , Γ′, δ′,q_0′,q_a′,q_r′)$ .

We want to construct a standard Tm that recognize L(M) ∩ L(M′). How do I go about it? I don’t have much more information than this. Anything to get started would be appreciated.