# Recursive languages and Turring Macheins

Page 1 of 1

## 1 Replies - 3199 Views - Last Post: 02 December 2012 - 03:03 PM

### #1 poonninja

Reputation: 1
• Posts: 1
• Joined: 15-June 09

# Recursive languages and Turring Macheins

Posted 29 November 2012 - 10:34 PM

Hey every one having a bit of a hard time with an assignment dealing with different types of languages and Turring Machines. Here is the problem in currently stuck on:

```Given any language L which is a subset of {0,1}*
define the language
unary(L) = { 0[sup]1x[/sup] | x is a member of L}
The language unary(L) is said to be unary since it is a subset of 0
For instance, if L = {0, 1, 11, 000} then unary(L) = {00, 000, 0000000, 00000000}. Show that L is  recursive if and only if unary(L) is recursive.

```

what i am trying to do at the moment is trying to use closure properties of recursive languages to transform any language into unary(L) of that language. I have a strong feeling after trying this for a few hours that i am on the wrong path. Can anyone give a hint please?

I also think that i dont fully understand what it means for a language to be recursive. If anyone could help explain that I would appreciate it!

Is This A Good Question/Topic? 1

## Replies To: Recursive languages and Turring Macheins

### #2 mojo666

Reputation: 375
• Posts: 811
• Joined: 27-June 09

## Re: Recursive languages and Turring Macheins

Posted 02 December 2012 - 03:03 PM

A language is recursive if there is an algorithm/Turing machine that halts and correctly identifies whether an input is in that language. I don't think closures are the way to go about this. Basic proving techniques are probably your best bet. Try and define an algorithm for Unary and Binary. [Binary(Unary(L)) = L]. If Unary(L) is recursive and we apply a halting algorithm to it, what does that say about the resulting language?