Back to marketplace
Models of Computation
No description yet. This curated deck is ready for daily study.
Total cards: 5•Content version: v4•Public deck•Updated: 8/1/2026
Card preview (5)
#1
Front (Question)
What is a finite state machine (FSM) ?
Back (Answer)
A representation of input A finite set of states A specification of state transitions Undefined transitions immediately crash the machine Has no memory of its history
#2
Front (Question)
What is a language?
Back (Answer)
A set of strings, potentially infinite build over a finite alphabet of symbols
#3
Front (Question)
Can you use FSM for language?
Back (Answer)
The answer is no because FSM has no memory which is required for language due to it having long-distance dependencies
#4
Front (Question)
What is a turing machine?
Back (Answer)
A finite state machine with a tape of infinitely many cells that may have symbols in them Infinite memory
#5
Front (Question)
Church-turing thesis
Back (Answer)
Any algorithm can be translated into an equivalent computation involving a Turing machine