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

#1 poonninja  Icon User is offline

  • New D.I.C Head

Reputation: 1
  • View blog
  • 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  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 408
  • View blog
  • Posts: 882
  • 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?
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1