Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Foundations 1 > Last test > Flashcards

Last test Flashcards

(100 cards)

Start Studying
1
Q

A turing machine is slightly more complicated than a finite-state machine.

A

T

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

No more powerful model exists than the Turing Machine.

A

T

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

The TM cannot get stuck in an infinite loop

A

F

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

The TM does not have weakness.

A

F

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

The TM is the strongest of computational mechanisms.

A

T

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

What is the most powerful type of automation?

A

TM

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

What is the one weakness of a TM?

A

It can get stuck in an infinite loop.

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

As soon as a TM enters an accepting state, what happens?

A

It halts the input string.

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

DFAs and NFAs can make transitions out of their accepting states, proceeding until all the input has been read and they often have more than one accepting state.

A

T

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

Each move of a TM is determine by the previous state and the future input symbol.

A

F

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

How far does the tape of a TM extend?

A

Infinitely.

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

In a TM, transitions leaving an accepting state are never used, so there is never any real need for more than one accepting state.

A

T

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

TMs do not have a separate location for storage.

A

T

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

Unlike a stack machines, TMs do not have a separate location for storage.

A

T

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

What controls the read/write head?

A

state machine

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

Where does the head on a TM start?

A

First symbol in the input string.

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

TM can easily handle all regular languages.

A

T

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

TM can easily handle every regular language, but cannot handle all context-free languages.

A

F

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

It is possible to take any stack machine and convert it into an equivalent TM using what as a stack?

A

the infinite tape.

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

An instantaneous description for a TM represents its entire configuration in a single string: the contents of the tape, the state, and the position of the head.

A

T

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

B is the blank symbol, B ∈ ∑, B ∉ Γ.

A

F

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

Becuase the leading Bs on the left and the trailing Bs on the right are suppressed, an ID is always an infinite string.

A

F (finite string)

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

How many Tuples does TM have?

A

7

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

What does an instantaneous description for a TM represent?

A

Its entire configuration in a single string: the contents of the tape, the state, and the position of the head.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
What does B represent in the formal definition of a TM?
B is the blank symbol, B ∈ Γ, B ∉ ∑.
26
What is (Q) in A TM M in the 7-tuple?
is the finite set of states
27
What is ∑ of 7-tuple M
Is the input alphabet
28
What kind of tuple is a TM?
A 7-tuple.
29
What type of description for a TM represents its entire configuration in a single string?
An instantaneous description.
30
A TM does not halt on a given input if it get stuck.
F
31
TM may run forever on a given input.
T
32
What are we define as extended relation |→* for?
Sequences of zero or more steps.
33
What happens to a TM if it ever reaches an accepting state?
The TM accepts the input.
34
Stack machines and NFAs can in no way run forever.
F
35
Stack machines are like Turning Machines in that they can run forever without using empty transitions.
F
36
How many possible outcomes are there when a TM runs?
Three.
37
A recursively enumerable language is one that is L(M) for some TM M.
T
38
A TM M is a total TM if F(M) = {}.
T
39
What are the three possible outcomes that may occur when a TM is run?
Accepted, rejected, runs forever
40
What is a language that is L(M) for some TM M?
Recursively Enumerable
41
What is a recursive language?
One that is L(M) for some TM M.
42
What is a total TM?
If and only if F(M)={}
43
What is the special name for TMs that halt on all inputs/
total TMS
44
List one of the important higher-level techniques of TM construction.
Marking cells
45
What does it mean to mark a cell in a TM?
Overwriting the symbol there with a marked version of that symbol.
46
A three tape TM model is easier to program that our basic model.
T
47
How many tapes are needed to record data from three TM?
3
48
We can always implement any infinte memory using the states of the TM.
F
49
What types of languages are recursive?
All regular and context-free languages are recursive.
50
All regular languages and all context free languages are recursive.
T
51
It is interpreter is a program that takes another program as input and carries out the instructions of that input program.
T
52
How many tape make TM that interprets any stack machine?
Three
53
How much of the tape on a TM does a DFA use?
Finite portion of each of its tapes.
54
A TM that acts as a TM-interpreter is called what?
Universal turing machine.
55
A TM that acts as an interpreter for another TM is called a universal machine.
T
56
All regular languages are also recursive.
T
57
What is a universal TM?
A TM can even act as a TM-interpreter.
58
Computability consists of unsolvable problems
F
59
Solvable problems range from the trivially simple to the hideously complicated.
T
60
What is the term that is mysterious border of our realm?
Computability.
61
In the definition of a Turing computable function, what is not considere?
Final state of the tM
62
The final state of the TM is not considered, nor does it matter where the TM's head is positioned when it halts.
T
63
The add function in TM arithmetic does not produce the simple binary sum as output after taking input of that form.
F
64
Using TM composition is a bit like using subroutines in a high-level language.
T
65
What is a TM composition is a bit like?
Using subroutines in a high-level laguage.
66
A TMs memory is like what?
Tape
67
To decrement a binary number is not a simple operation closely related to addition.
F
68
To get to a particular cell in a TM's memory, what do you have to do?
Move the TM's head there one step at a time.
69
What is decrementing a binary number?
Subtracting one from it.
70
For every language L we can define a corresponding function.
T
71
Function implementation and language definition are the exact same perspective on different computational problems.
F
72
To get to particular cell in a TM machine you move the TMs head there, a couple of steps at a time.
F
73
With suitable conversions between different kinds of data, it turns out that all those formalizms for computation will never be interconvertible.
F
74
For every function f we cannot always define a corresponding language.
F
75
In spite of their apparent simplicity, TMs can do anything that can be done with a high-level programming language on a modern computer.
???
76
In what TMs can do anything that can be done with a high-level programming language?
??
77
It is easy to show that the language is recursive if and only if the funciton is Turing computable.
F
78
TMs can be used to implement Boolean logic.
T
79
TMs can be used to index memory using binary addresses.
T
80
What can Turing machines be used for?
Implementing Boolean logic.
81
A function that is Turing computable (like addition on binary numbers) is called what?
computable function
82
A language that is recognized by some total TM is called decidable.
F
83
A language that is recognized by some total TM is called what?
Recursive
84
Any formalism for computation that is interconvertible with TM is said to be Turing equivalent.
T
85
Any TM can be simulated by a Post system and Vice Versa.
T
86
In 1936, who all suggested that their equivalent formalisms had in fact captured the elusive idea of 'effective computational procedure.'
Alonzo Curch and Alan Turing.
87
The meaning of effective computational procedure is close to what term?
Algorithm
88
Turing and Church Theorem suggested that computability by a total TM be taken as the definition of computability.
T
89
What doe you call a function that is Turing computable?
Computable.
90
What do you call a language that is recogniazed by total TM
Recursive Language
91
what is another common name for Church's Thesis?
Church-Turing Thesis
92
What is the term peopel use for any formalism for a computer that is interconvertable with TM?
Turing Equivalent
93
When there is some total TM that decides whether an input has a certain property, we say the property is decidable.
T
94
For any Java program there is an equivalent TM/
T
95
It is possible to construct universal TMs that interpret other TMs encoded as what?
Input strings.
96
A TM can do a better job of implementing a high level language than an ordinary computer.
T
97
In sense, physical computers are more like DFAs than TM - DFA's with enormous, but still finite, state sets.
T
98
In what way are computers more like DFAs than Turing machines?
They have finite state sets.
99
There is something that high-level languages can do that TMs cannot do.
F??
100
TM can do a job of implementing high-level lanuages better than what?
Modern computers.

Foundations 1 (5 decks)

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