Sorry I know its shit to make a thread just for a single question but my prof refuses to provide any insight or help doing a practice exam question. Im the one typing sentences in the email and he replies with 2 words either yes or no proving no insight in what im doing is wrong
I figure its better off if one of you can explain to me this question.
I believe the answer is false, because if we take a regular language , say L(TM) = {0}, we know the complement L'(TM) = {everything that isn't 0} (Assume the Language is over a binary alphabet). So if it were the case that L
I understood what you were saying until you got to L
Leo Carter
Sorry, L
Adrian Reed
So the question is whether everything in A' is reducable to 0?
Wyatt Young
I can answer but you have to some services for me first
Ayden Reed
Im not 100% sure the converse holds, but the question is asking is L mapping reducible to L' (Is any decidable language reducible to its complement)
What you want
Bentley Hughes
You have to give me that hot bubble butt of yours
Xavier Brooks
Ok so I just looked up some definitions. A is the alphabet {0} and it is a subset of (0|1|B)*. A' is an alphabet that is also a subset of the same thing. According to this picture, since A and A' are both subsets of the same sigma ((0|1|B)*), then there needs to be a computable (bijective ?) function f that maps from A to B. If such a function existed, A and A' would be isomorphic, and if they're isomorphic they would have the same cardinality. Unfortunately A has a cardinality of 1 and A' has a cardinality of infinity. I don't think it's true, but I'm also really new to all this stuff
Cooper Gomez
oops I wrote B but I meant A'
Blake Diaz
Im getting really confused now, just to confirm, the "if and only iff or "iff" " means that if theres an element x in A, then theres an element f(x) in B, Similarly, if theres an element in B then there must be some element y in A that gives f(y) which was the element in B. Does this sound right? Im questioning my foundation of everything right now
Cooper Lopez
Yes that's exactly right.
So you couldn't just assign f(x) = 1. Sure, for all x in A ({0}), f(x) is in A'. But, you can pick several things in A' where there is no element x in A so that f(x) = that thing.
Hunter Allen
Yes this was my reasoning, apparently it is not correct.
I understand most of it, but I cant see how this disproves my claim. So confused as to why what im saying is wrong
Ryan Barnes
you should (also) ask in /sci/ it might be a better place than here. :^) if I wasn't in bed already i would try to answer but good luck!
Levi Lee
(disclaimer, been a LONG while since I took a formal language class. This might be complete nonsense. Don't blame me if you use this answer and get this wrong on your homework. Sorry your prof is being an asshat and you have to ask Sup Forums for homework help. I suggest you try some IRC channels instead.)
A language is turing decidable if and only if there exists a turing machine that accepts on some language L and rejects on anything not in L.
Note that there is a meaningful distinction between a rejection state and not halting. If we say that a language is turing decidable, it means necessarily that this will reach a rejection or acceptance state.
So with the question in the pic on the OP, we know that we have a turing decidable language A, and that there exists a turing machine that will tell us, definitively, if an input is in A, and if it is not in A.
Therefore, the answer is true. It doesn't matter that A' is an infinite set, it will simply enter an accepting state as soon as it is certain that it hasn't seen something in A, the same way that the TM for A will enter a rejection state as soon as it is certain it hasn't seen something in A.
Chase White
So it looks like they defined f as a turing machine such that f(0) = 1 (just an example, w2 in their work) and f(anything else) = 0. That would work. I guess it doesn't have to be bijective
Jonathan Mitchell
disregard this, saw your link to that ucsd homework, I'm wrong.
So in other words this procedure is done to construct L', we don't actually start off with it? That doesnt make much sense, if we start off with a Language we already know its complement, so the problem should be whether or not we can construct the function that maps elements from L to L'.
I had assumed that its impossible to construct the function because something like 101 which is in L' wouldn't be possible to be mapped to, not even sure if I understand properly
Wyatt Walker
Yes Ive read it at least 10 times over, what theyre doing doesnt prove anything, as they put it, no matter what "w" you simulate on the tm you will never get something other than the result of f(0) since theres only one thing in L. Its impossible to ever get elements such as 01, 101,1010101010, 0100000, or whatever which are all in L'.
