Brainscape's Knowledge GenomeTM

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


See full index

Foundations 1 > Last test > Flashcards

Last test Flashcards

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
Q

What does B represent in the formal definition of a TM?

A

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

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

What is (Q) in A TM M in the 7-tuple?

A

is the finite set of states

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

What is ∑ of 7-tuple M

A

Is the input alphabet

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

What kind of tuple is a TM?

A

A 7-tuple.

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

What type of description for a TM represents its entire configuration in a single string?

A

An instantaneous description.

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

A TM does not halt on a given input if it get stuck.

A

F

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

TM may run forever on a given input.

A

T

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

What are we define as extended relation |→* for?

A

Sequences of zero or more steps.

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

What happens to a TM if it ever reaches an accepting state?

A

The TM accepts the input.

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

Stack machines and NFAs can in no way run forever.

A

F

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

Stack machines are like Turning Machines in that they can run forever without using empty transitions.

A

F

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

How many possible outcomes are there when a TM runs?

A

Three.

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

A recursively enumerable language is one that is L(M) for some TM M.

A

T

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

A TM M is a total TM if F(M) = {}.

A

T

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

What are the three possible outcomes that may occur when a TM is run?

A

Accepted, rejected, runs forever

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

What is a language that is L(M) for some TM M?

A

Recursively Enumerable

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

What is a recursive language?

A

One that is L(M) for some TM M.

42
Q

What is a total TM?

A

If and only if F(M)={}

43
Q

What is the special name for TMs that halt on all inputs/

A

total TMS

44
Q

List one of the important higher-level techniques of TM construction.

A

Marking cells

45
Q

What does it mean to mark a cell in a TM?

A

Overwriting the symbol there with a marked version of that symbol.

46
Q

A three tape TM model is easier to program that our basic model.

A

T

47
Q

How many tapes are needed to record data from three TM?

A

3

48
Q

We can always implement any infinte memory using the states of the TM.

A

F

49
Q

What types of languages are recursive?

A

All regular and context-free languages are recursive.

50
Q

All regular languages and all context free languages are recursive.

A

T

51
Q

It is interpreter is a program that takes another program as input and carries out the instructions of that input program.

A

T

52
Q

How many tape make TM that interprets any stack machine?

A

Three

53
Q

How much of the tape on a TM does a DFA use?

A

Finite portion of each of its tapes.

54
Q

A TM that acts as a TM-interpreter is called what?

A

Universal turing machine.

55
Q

A TM that acts as an interpreter for another TM is called a universal machine.

A

T

56
Q

All regular languages are also recursive.

A

T

57
Q

What is a universal TM?

A

A TM can even act as a TM-interpreter.

58
Q

Computability consists of unsolvable problems

A

F

59
Q

Solvable problems range from the trivially simple to the hideously complicated.

A

T

60
Q

What is the term that is mysterious border of our realm?

A

Computability.

61
Q

In the definition of a Turing computable function, what is not considere?

A

Final state of the tM

62
Q

The final state of the TM is not considered, nor does it matter where the TM’s head is positioned when it halts.

A

T

63
Q

The add function in TM arithmetic does not produce the simple binary sum as output after taking input of that form.

A

F

64
Q

Using TM composition is a bit like using subroutines in a high-level language.

A

T

65
Q

What is a TM composition is a bit like?

A

Using subroutines in a high-level laguage.

66
Q

A TMs memory is like what?

A

Tape

67
Q

To decrement a binary number is not a simple operation closely related to addition.

A

F

68
Q

To get to a particular cell in a TM’s memory, what do you have to do?

A

Move the TM’s head there one step at a time.

69
Q

What is decrementing a binary number?

A

Subtracting one from it.

70
Q

For every language L we can define a corresponding function.

A

T

71
Q

Function implementation and language definition are the exact same perspective on different computational problems.

A

F

72
Q

To get to particular cell in a TM machine you move the TMs head there, a couple of steps at a time.

A

F

73
Q

With suitable conversions between different kinds of data, it turns out that all those formalizms for computation will never be interconvertible.

A

F

74
Q

For every function f we cannot always define a corresponding language.

A

F

75
Q

In spite of their apparent simplicity, TMs can do anything that can be done with a high-level programming language on a modern computer.

A

???

76
Q

In what TMs can do anything that can be done with a high-level programming language?

A

??

77
Q

It is easy to show that the language is recursive if and only if the funciton is Turing computable.

A

F

78
Q

TMs can be used to implement Boolean logic.

A

T

79
Q

TMs can be used to index memory using binary addresses.

A

T

80
Q

What can Turing machines be used for?

A

Implementing Boolean logic.

81
Q

A function that is Turing computable (like addition on binary numbers) is called what?

A

computable function

82
Q

A language that is recognized by some total TM is called decidable.

A

F

83
Q

A language that is recognized by some total TM is called what?

A

Recursive

84
Q

Any formalism for computation that is interconvertible with TM is said to be Turing equivalent.

A

T

85
Q

Any TM can be simulated by a Post system and Vice Versa.

A

T

86
Q

In 1936, who all suggested that their equivalent formalisms had in fact captured the elusive idea of ‘effective computational procedure.’

A

Alonzo Curch and Alan Turing.

87
Q

The meaning of effective computational procedure is close to what term?

A

Algorithm

88
Q

Turing and Church Theorem suggested that computability by a total TM be taken as the definition of computability.

A

T

89
Q

What doe you call a function that is Turing computable?

A

Computable.

90
Q

What do you call a language that is recogniazed by total TM

A

Recursive Language

91
Q

what is another common name for Church’s Thesis?

A

Church-Turing Thesis

92
Q

What is the term peopel use for any formalism for a computer that is interconvertable with TM?

A

Turing Equivalent

93
Q

When there is some total TM that decides whether an input has a certain property, we say the property is decidable.

A

T

94
Q

For any Java program there is an equivalent TM/

A

T

95
Q

It is possible to construct universal TMs that interpret other TMs encoded as what?

A

Input strings.

96
Q

A TM can do a better job of implementing a high level language than an ordinary computer.

A

T

97
Q

In sense, physical computers are more like DFAs than TM - DFA’s with enormous, but still finite, state sets.

A

T

98
Q

In what way are computers more like DFAs than Turing machines?

A

They have finite state sets.

99
Q

There is something that high-level languages can do that TMs cannot do.

A

F??

100
Q

TM can do a job of implementing high-level lanuages better than what?

A

Modern computers.

Foundations 1 (5 decks)

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