Skip to main content

Questions tagged [encoding-scheme]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
7 votes
2 answers
16k views

What is an "encoding" of a TM?

I'm currently working on a reduction from $A_{TM}$ to another language, and have been reading through some example proofs. I've come across the situation where, for example, we have $L = \{ \langle M,...
user3472798's user avatar
5 votes
3 answers
476 views

Defining computable functions on arbitrary sets

Turing machines take inputs that are strings of symbols from some alphabet, and they give outputs that are strings of symbols from the same alphabet. To show that a function is computable, we have to ...
N. Virgo's user avatar
  • 976
5 votes
1 answer
11k views

When would the worst case for Huffman coding occur?

I am doing a project on Huffman coding and wanted to know when it wouldn't be ideal to use or rather when would the Huffman coding produce low compression. Since it mainly revolves around the ...
user avatar
5 votes
1 answer
6k views

A string representation of any Turing machine

The set of all Turing machines is said to be countable. The central idea of the proof of this fact is that every Turing machine can be written as a finite string of characters. I am having trouble ...
AmadeusDrZaius's user avatar
3 votes
3 answers
2k views

Reconstructing files from binary

Popular view tells us that any kind of information is just a collection of bits, that is zeroes and ones placed in a particular order. I was thus having this thought. Suppose that I have some kind of ...
Kurt's user avatar
  • 133
1 vote
1 answer
104 views

What is responsible for the 1-1 correspondence between characters and binary?

Could someone explain to me what component(s) are responsible for translating binary into ASCII/UNICODE? For example, is it an assembly program that sets up a 1-1 correspondence between characters and ...
Steven's user avatar
  • 13