## Undecidability of the language of all Turing Machines with repeat strings as their language

Show that the language consisting of all Turing machines whose language consists of strings that can be broken up into two consecutive and equal strings is undecidable.

I would prefer if reduction was used and not Rice’s theorem.

Posted on Categories proxies

## 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?

Posted on Categories proxies

## Is LXD virtualization as isolated and secure as KVM virtual machines?

Stumbled upon a privacy conscious hosting provider that uses LXD vs KVM to manage user VPS instances.

My understanding is KVM is more isolated so using LXD doesn’t make sense from a privacy perspective.

Perhaps I am missing something?

Posted on Categories proxies

## 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

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 🙂

Posted on Categories proxies

## 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.

Posted on Categories proxies

## 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?

Posted on Categories proxies

## 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.

Posted on Categories proxies

## 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.

Posted on Categories proxies

## 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.

Posted on Categories proxies