[thatguynooneknows]

Ive just had a lecture and lesson about Computability, Decidability and Acceptability. And honestly, I dont have a clue what he was talking about.

No-one is my class has any idea what to do (and none of them really care tbh) but its really annoying me that I cant wrap my head around this.

Ill give you the example question and the answer we got in class and if someone could explain it to me I will love you! =]



(had to add as image as contains some images in the question)

If you don't understand it either then that might make me feel better too :P

Thanks

(P.S. I have asked the tutor to explain this to me and he has, but I didn't understand what he said really =/)

[Choad]

that makes[1] (if true) about as much[2]*sense to me as (th[1]$)

why write like that? why not use english? seems slightly counter productive when you're trying to teach someone something

[thatguynooneknows]

Originally Posted by Choad

that makes[1] (if true) about as much[2]*sense to me as (th[1]$)

why write like that? why not use english? seems slightly counter productive when you're trying to teach someone something

Im not sure what your getting at exactly.
but the numbers (1) and (2) that are blue in brackets are links to the questions 1. and 2. so you know what theyre talking about. pointless really but whatever.

[caaakeeey]

I think its saying that (2) can be rewritten in the form of (1) - (by hardcoding any input i), so they are essentially the same algorithm.

[caaakeeey]

Also, out of interest, which University do you go to?

[thatguynooneknows]

Originally Posted by caaakeeey

I think its saying that (2) can be rewritten in the form of (1) - (by hardcoding any input i), so they are essentially the same algorithm.

No i dont think it is.
It's something to do with finding out if an algorithm is computable (i.e. if it will ever halt or if it will infinitely loop) I havnt really given enough information for people who dont know about computability to understand it but i was hoping there might be an AP&D genius on here somewhere =P

Originally Posted by caaakeeey

Also, out of interest, which University do you go to?

And I go to Huddersfield

[caaakeeey]

I'm pretty sure it is.

It is saying that any algorithm with any input such as:

def a(input):
    #/...
    #...
    #.../
    return whatever

Can ALWAYS be rewritten like;

def b():
    input = i #this can be hardcoded to *any* input that the previous algorithm takes
    return a(input)

If b halts, then a must halt.
If you can work out whether b halts then you must have found a way to see if a halts.

Does that help?

[laser]

What you need to show is that if this problem has a solution, then the halting problem has a solution. You need to express this problem in terms of the halting problem, and therefore you can imply that if this problem is decidable, that would mean the halting problem is.

I always thought of it like a box. This box has different things connected together to get a result out of the other end. If one of the things that is connected together is a mythical box that solves the halting problem, and is part of the solution, then the solution can not be solved without the halting problem being solved.

[Talon]

What course are you doing? Thats all ancient egyptian to me.

[thatguynooneknows]

Originally Posted by laser

What you need to show is that if this problem has a solution, then the halting problem has a solution. You need to express this problem in terms of the halting problem, and therefore you can imply that if this problem is decidable, that would mean the halting problem is.

I always thought of it like a box. This box has different things connected together to get a result out of the other end. If one of the things that is connected together is a mythical box that solves the halting problem, and is part of the solution, then the solution can not be solved without the halting problem being solved.

hmm, that makes a lot more sense than what he was saying.
Im still a bit confused but i think a bit more reading and using that kind of logic i might be able to grasp it.

thnakyou =]

Originally Posted by caaakeeey

If b halts, then a must halt.
If you can work out whether b halts then you must have found a way to see if a halts.

Does that help?

And yeah that helps too,
its starting to make sense *feels happy*
itll still take me some time to get it fully but youve all helped a lot =]

thanks

Originally Posted by Talon

What course are you doing? Thats all ancient egyptian to me.

Im doing Computing Science, In my second year.

[Talon]

Originally Posted by thatguynooneknows

Im doing Computing Science, In my second year.

Hmm. I never had a lesson like that when I did my degree...

[laser]

Originally Posted by Talon

Hmm. I never had a lesson like that when I did my degree...

Where did you do your degree? You need to know this stuff to understand things like P=NP, so you'll have covered it then

[Talon]

Uea...p=np?

[caaakeeey]

I'll assume UEA isn't heavy on theory then =p

[Talon]

There is rather a lot actually, though it appears to focus on the important stuff.

[-Em-]

Originally Posted by Talon

There is rather a lot actually, we just only focus on useful stuff.

You'd think that whether or not a problem was tractable in a reasonable time, never mind at all, would be a pretty useful thing to know

[laser]

P=NP is probably one of the most important questions in Computer Science.

[Talon]

Put it in words and I may know what you are on about.

In the event that I dont know it Im getting on just fine without it .

[-Em-]

Originally Posted by Talon

Put it in words and I may know what you are on about.

In the event that I dont know it Im getting on just fine without it .

"Do all problems in the complexity class NP (i.e Those for which there exists a polynomial time algorithm for deciding whether a given answer to that problem is correct) fall into the complexity class P (i.e. There is a polynomial time algorithm for generating a correct answer to the problem)?"

[PieMaster]

Originally Posted by Talon

Put it in words and I may know what you are on about.

In the event that I dont know it Im getting on just fine without it .

I think we had it split out, so the 'theory' was covered in the first year maths modules, then the impact on algorithims was done in S2A23.