Galders speedy courier, definition of “mineral goods”

The 4th level spell, ‘Galder’s Speedy Courier’, has the following material component cost: (25 gold pieces, or mineral goods of equivalent value, which the spell consumes)

I assume we can agree that "mineral goods" falls under the category ‘object’ as defined here What is considered an object?

My questions:

  1. Is there a clear definition in 5e, of what the term "mineral goods" encompasses, or is it perhaps possible to extrapolate a definition?

  2. Which of the following examples, then qualifies as acceptable material casting components? 25gp worth of:

Gems?

Salt?

Swords? (Enough of them, so that the raw amount of iron equals 25gp worth)

A copper statue? (A raw amount of copper that equals 25gp worth, ignoring its artistic value)

A somewhat heavy gold necklace?

A big pile of gold rings?

Gems and salt seem obviously acceptable. But would using swords, statues or jewelry qualify?

Definition of ‘Record’

Given the definition of ‘record’: "a collection of field values for a given entity", is this a set of field values for ALL the fields of the entity, or only one particular field [so that you get a different set for each field]? Also, is the relationship b/w a field & field value essentially equivalent to a function?

NOTE: Total beginner learning data struc. & algos.

What is the definition of “creature” and is it used consistently?

In the Starter set and Basic Rules, it mentions “character”, “non-player character”, “player character”, “monster”, “creature”, and maybe other terms I’ve missed. Which of these terms are interchangeable?

Some examples from the Basic Rules PDF:

  • Page 105: Conditions Appendix refers only to creatures.

  • Chapter 11: all spell descriptions refer to creatures, but occasionally other terms such as humanoids.

Confusion about definition of languages accepted by Turing Machine, very basic question

I’m studying for an upcoming exam and my book gives the following definition:

Let $ M$ be a Turing machine, then the accepted language $ T(M)$ of $ M$ is defined as $ T(M) = \{x \in \Sigma^* \mid z_0 x \vdash^* \alpha z \beta; \alpha, \beta \in \Gamma^*; z \in E\}$ .

As a side note, $ \vdash$ denotes the transition from one configuration of the TM to the next, and the $ ^*$ denotes an arbitrary number of applications of this relation.

What I’m confused about is that under this definition of acceptance, I only have to enter the end state once and even if I leave it, the word would be accepted, or I could loop in this end state. In push down automata or regular automata, we do not have this problem as we move through the word sequentially from beginning to very end, especially in push down automata where the stack is separated from the input word.

Now I read in most other definitions, additionally to ending up in an end state, the Turing machine must also halt, meaning that it must end in a state that has no transitions. Although I’m not sure what this would mean for deterministic Turing machines as they have to have transitions for all configurations of the machine.

To wrap it up:

Question 1: Is halting required? Is it a useful property for accepting languages or is there a reason the definition was given as is?

Question 2: How would you define "halting" for deterministic Turing machines?

The definition of a graph’s transitive reduction

I want to determine the transitive reduction of this graph:

1

as of now, I only found the first step of doing this: represent the transitive closure of the graph as an adjacency relation, so this is what I did:

 (a,b)  (a,c)  (a,d)  (a,e)  (b,d)  (c,d)  (c,e)  (d,e) 

I’m not sure that this is the correct transitive closure of the graph, and I don’t know how to move forward in determining its transitive reduction.

Understanding definition of #P [migrated]

Valiant defined $ \#P$ in terms of a counting TM, which is a NTM that outputs the number of solutions [1].

I am a bit stuck with the following two questions: Let’s say I have a decision problem $ X$ , the corresponding counting problem $ \#X$ , and an enumeration algorithm $ E$ that enumerates the solutions of $ X$ in polynomial output complexity.

  1. If $ w$ is a witness for $ X$ that I can verify in polynomial time, does this imply that $ \#X$ is in $ \#P$ ?
  2. Does the existence of $ E$ imply that $ \#X$ is in $ \#P$ ?

For both questions, I think the answer is yes because they imply that there is a NTM which could be modified to count the number of witnesses. However, I feel like I cannot argue this properly and that I might miss something.

[1] Leslie G. Valiant: The Complexity of Computing the Permanent. Theor. Comput. Sci. 8: 189-201 (1979)

Does the heap property in the definition of binary heaps apply recursively?

The definition of binary heaps says that it should be a complete binary tree and it should follow the heap property where according to the heap property, the key stored in each node is either greater than or equal to or less than or equal to the keys in the node’s children.

Binary tree

In the above tree, the node with value 70 is greater than its parent 10 breaking the heap property. However, 70 is also greater than 40 and lies in the subtree of 40. Will we say that the heap property is also breaking at 40, even though 40 is greater than its two children 10 and 2?

How to understand definition of $\Pi_k$ in arithmetical heirarchy

Am reading a text about computability theory, and according to the text, at each level $ k$ of the arithmetical hierarchy, we have two sets, $ \Sigma_k$ and $ \Pi_k$ , where $ \Pi_k$ is defined as:

$ $ \Pi_k=co-\Sigma_k $ $

So that for $ k=0$ , we have the class of decidable sets and $ \Sigma_0=\Pi_0$ , and for $ k=1$ , we have $ \Sigma_1$ as the class of computably enumerable (c.e.) sets and $ \Pi_1$ as the class of not computably enumerable sets (not c.e.)….

Let $ L(M_e)$ denote the language recognized by Turing Machine $ M_e$ with Godel number $ e$ . I came across the following language $ E$ , where:

$ $ E=\{e|L(M_e)=\Sigma^*\}$ $

i.e. $ E$ is the language of all Turing Machine codes $ e$ that are computably enumerable. By a diagonalization argument, it can be shown that $ E$ is not c.e. This implies that:

$ $ E \in \Pi_1 $ $

However, if $ E \in \Pi_1$ , it means that $ E = co-A$ , for some $ A \in \Sigma_1$ , using the definition in the above statement… However, the complement of $ E$ is:

$ $ \overline{E}=\overline{\{e|L(M_e)=\Sigma^*\}} $ $

which (I guess) means that $ \overline{E}$ is the language of all Turing Machines $ e$ such that on some inputs, $ e$ diverges… However, it has been shown that $ \overline{E} \equiv_m K^{2}$ , i.e. $ \overline{E} \equiv_m K^K$ , so that, where given two sets $ A$ and $ B$ , we have $ A \equiv_m B$ iff $ A \leq_m B$ and $ B \leq_m A$ , and $ \leq_m$ refers to a many-to-one reduction:

$ $ \overline{E} \equiv_m K^K \in \Sigma_2 $ $

Given that $ \Sigma_2 \neq \Sigma_1$ , it looks like that $ \overline{E}$ is not computably enumerable… But doesn’t this contradict the definition of $ \Pi_1$ which states that the complement of a not c.e. set is c.e. ?

I think am missing something in my understanding of the definitions …