Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Theory of Computation > Decidability and Reducibility > Flashcards

Decidability and Reducibility Flashcards

1
Q

What is a decidable language?

A

There is a Turing machine that always halts with this language

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
1
Q

What is the halting problem?

A

Is it possible to write a program that determines whether another program halts?

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What are the three things under decidable?

A

Acceptance, Emptiness and Equivalence

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q
A
How well did you know this?
1
Not at all
2
3
4
5
Perfectly

Theory of Computation (5 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions